How do digital oscilloscopes achieve such high sample rates?

I presume they use Flash ADCs. These have the advantage that the conversion is immediate, while SA (Successive Approximation) ADCs like used in most microcontrollers perform an algorithm that requires a number of steps. A disadvantage of Flash ADCs is that they are rather heavy on hardware (an 8-bit ADC has 255 comparators), but most scopes don't have very high resolution. (Analog scopes often were 3% accurate, which translates to 5 bit.)

The entry level DSO Rigol 1052E (the one I own and 100 MHz capable with software change) uses an Analog Devices AD9288. This is a dual channel ADC with 8 bit parallel outputs and samples at either 40 or 100 million samples per second (depending on speed grad of chip). Although the Rigol is a 1 Gig samples per second, so I'm not sure if they are multiplexing these or what exactly is giving them 10x the samples of the single chip.

The AD9288 has bit-per-stage pipeline type converter for the 5 MSB bits and uses a 3-bit flash for the final 3 LSB. This makes sense, as the higher magnitude should be easier to convert fast with pipelines. As your ADC speeds go up, the number of bits sampled via flash conversion will increase, as steven said.

Jodes, your comment says you got your answer, but there's much more to the solution than Flash ADCs. Have a look at Agilent's Application Note, "Techniques to Achieve Oscilloscope Bandwidths of Greater Than 16 GHz." I used to work on that campus (but don't claim to have detailed scope experience). Agilent in Colorado Springs is the global hub of knowledge related to multi-gigahertz signal processing. They worked on a 32GHz solution for years and just started shipping last year. The active probes and microelectronics that do the signal processing are extremely sophisticated. Check out the entire library of documents related to Agilent's Infiniium 90000 X-Series high-performance DSO and DSA oscilloscope. Google it -- the URL is ugly and I'm not sure they offer a permanent link to the library page. You might also want to have a look at the related patents.