For every point in the cubemap, the colour is calculated by finding the lighting on a surface whose normal points from the center of the cube to that point. Here it's calculated from a few directional sources (the sun and a reddish planet). It's also possible to calculate the diffuse lighting cube using a cubemap image of the scene.
Only one texture lookup into the precalculated cubemap is needed at runtime. The result is very fast calculation of an unlimited number of light sources (in the case of a source cubemap, effectively you have one tiny light for every pixel).
Ambient occlusion
Left: Diffuse cubemap only. Notice that there are no shadows - the engine ports are far too bright on the inside.
Right: Diffuse cubemap mixed with ambient occlusion texture, calculated with ATi's NormalMapper. This texture describes how much of each point on the object's view of the surrounding scene is obstructed. This gives simple self-shadowing.
(click to see the occlusion texture map)
In this example, light is coming evenly from every direction. Decent soft shadows are achieved with no runtime cost. The downside is that this only works with static models - the models can be moved around, turned, etc., but they cannot change shape (for example, bending at a joint). There are some artifacts visible; using more samples per texel helps but takes longer to generate.
A more sophisticated approach such as PRT allows taking the direction of incoming light into consideration (as is, the shadows are only correct for uniform light)
Edit: never mind.