The HD Voice service is using a codec called Adaptive Multi-Rate Wideband (AMR-WB), instead of the existing AMR codec that we've all come to know and loathe. AMR-WB was first tested back in 2006, although it has taken this long for the industry to agree on a standard for high quality 3G calling. In parallel to its development, Nokia developed the Variable-Rate Multimode Wideband (VRM-WB) codec which is compatible with AMR-WB.
The aim of AMR-WB is to squeeze in more signal information while not consuming more bandwidth on the network. It achieves this by taking audio samples from a broader frequency range (50–7000Hz) than the AMR codec sampled over (300–3400Hz). The adaptive aspect of the technology is that the the codec will increase its bit rate to adapt to more complex speech patterns. For example, just saying "Hmm, yes, interesting" in a quiet background may only take 6.60 Kbits per second, whereas having a much more involved conversation in a noisy environment with words of varying length will go up to 23.85 Kbits per second.
While this development should make mobile phone calls less of a painful experience, don't expect to be taking part in a HD Voice call for some time yet. For now it will only be Orange to Orange calls on supported devices. Even though Orange and T-Mobile have agreed to merge, their networks are still separate, so the latter's users will not yet benefit from the service. The handsets supported by Orange for HD Voice are described as "new variants" (i.e. custom firmwares to enable the codec), and according to Endgadget (source), customers who already own the correct models won't be receiving a firmware patch to enable the new service. It is also unlikely that most landlines would support use of this codec, even if it were incorporated into exchanges, there is great variability in the quality of the last 100 metres of buildings' phone lines.
Orange customers can find out more by clicking here.
Finally, here's a test call conducted by the Engadget UK Mobile team: