I don't understand how the camera can work out the white-balance to use in a given scene.
I could see it working if there is an obvious colour-cast (for example: under fluorescent lights). Does it compare the histograms from the different colour channels and try to make them match up to some degree? Even then I can only imagine it working reliably in very well-defined circumstances.
Can someone explain how it is implemented in today's cameras, and how well it typically works?
The original assumption is that the average scene should be color neutral and therefore by computing the average color in the scene and then applying the same correction to every pixel you would get a scene whose average color is neutral which should have the correct white-balance. This will fail when there is a dominant color and the scene.
Algorithms got more sophisticated over the years with lots of technical papers and patents written on the subject. They added more intelligence like clamping to the set of known illuminants.
The exact algorithm differs between cameras and it seems to work extremely well outdoors during the day, where there is little variation. Under artificial light there is much more variance and it is rather hit or miss. Older digital cameras were particularly bad but it has been improving on average.
The very best white-balance performance I've ever seen was on the HP Photosmart R967. DC Resource noticed this and commented that they should win the Nobel prize! Several recent compact cameras also do an excellent job. The advantage of a mirrorless camera over a DSLR for this is that it can read data from all over the sensor. DSLRs can now do that in Live-View mode.
Some DSLRs use an entirely different approach which is to measure white-balance instead. This is the case for the Olympus E-5. It has a dedicated 'external' sensor which measures the light falling on the camera. You can turn this off for cases when you are shooting from a different lighting than your subject.
The camera can't know what white balance to use, it can only make a guess based on the image data (or sometimes an external sensor, as Itai mentioned in his answer).
If I for example take an image of a blue wall, the camera thinks that I have taken an image of a gray wall in blue light, and the image ends up gray instead of blue. (This is pretty much the same phenomenon as when I photograph a white or black wall with automatic exposure, and the camera sets the exposure so that both end up gray.)
I always use automatic white balance, and adjust it manually when devloping from the raw image. My experience is that sometimes the automatic white balance is spot on, most of the time it's very close, and in some rare sitations it's way off.
Note also that the "correct" white balance setting isn't always the exact color temperature of the light source. Sometimes an image needs a slight color change to look natural, and some may even need quite a lot. An image taken in bright sunlight may need to be slightly more yellow, and an image taken in the blue hours may need a lot of blue.
The answer is as varied as the many different models of cameras and their related firmware.
When set to AWB, most older digital cameras (including pretty much all of them around when this question was asked) use algorithms that attempt to set white balance based on the assumption that the brightest areas in the frame should be neutral white or very light gray. This works fairly well unless some areas are fully saturated in all three channels (before any exposure adjustments are applied).
The result may be similar to one of the preset selections available (Daylight, Tungsten, Cloudy, Fluorescent, etc.) or it may be considerably different from any of them. If the detected scene is close enough to one of the camera's preset choices, that one might be applied or might not, depending upon the exact camera model in question.
Newer cameras often use more sophisticated algorithms that can vary greatly from one camera model to the next. Most top tier models are similar to some forms of metering such as Nikon's 'Matrix' or Canon's 'Evaluative' metering in which the data from the frame is compared to a library loaded into the camera's firmware and applied based on instructions for the closest match. If the camera detects a scene with bright blue sky in the upper part of the frame and darker green in the lower frame it will apply WB based upon a landscape profile. If it detects a scene with lots of areas that look (to it) like skin tones it will apply a WB based upon a portrait profile. (This explanation is vastly simplified from the many subtleties that are analyzed and can affect the outcome.)
Some cameras even allow user selectable options between bias towards the brightest areas of the scene or bias towards the more average areas of the scene. Canon calls the two choices available with some of their newest models 'white priority AWB' or 'ambience priority AWB'.
