
Normal maps are images that store normals directly in the RGB values of an image. It's a popular method in 3d games and render software to achieve very realistic mapping of fake 3d reliefs.
Normal maps in Blender store a normal as follows:
Red maps from (0-255) to X (-1.0 - 1.0)
Green maps from (0-255) to Y (-1.0 - 1.0)
Blue maps from (0-255) to Z (0.0 - 1.0)
Since normals all point towards a viewer, negative values are not stored. In Blender we store a full blue range, although some other implementations also map blue colors (128-255) to (0.0 - 1.0). The latter convention is used in "Doom 3" for example.
Creating normal maps in Blender is very easy. Just use the "Nor" as "Map Input", and use a Blend texture to define the gradient. Copy this to three texture channels, and set the coordinates for mapping appropriate to only map X, Y or Z.
For highest resolution you can also force the Blue component (Z) to only map to positive values.
A sample .blend file with such a Material can be downloaded here.
Don't forget to render such maps with an Ortho camera, to get the widest range of normals, and no perspective distortion.

Settings for creating a normal map. From left to right:
Using Normal Maps is as simple as setting the "Normal map" button in the Image Panel in the Texture buttons, and make sure you apply this in the Material buttons "Map To" panel on "Nor".
The picture below uses the Normal Map and Color Map from the relief as rendered above. Note that this is just a rendering of a flat plane!
Since only the normals get affected during render, you will not get shadow or AO or other '3D' effects. It's still just a texture.
Officially the 2.36 release was for fixes only, but we couldn't resist to at least "fix" this in Blender.
It is imortant to note that the current support for normal maps isn't finished still. Two important additions can be expected in a new release;