(also known as a Bump Map)
Say you start with this texture (this is also known as the diffuse map):

This is an example of a normal map for the above texture:
The colours of the normal map tell your graphics card which parts of the surface are raised, and which are lowered, affecting the brightness/darkness according to the direction of the surrounding light sources.
The blue/green/pink colours are seldom made by the user. Many graphics programs come with a normal map generator, which creates the normal map based on a source image. In the above example, the normal map was made from the diffuse map. Darker areas became dips/cracks, and lighter areas became bumps.
There will be times when the colours in the source image do not represent bumps and dips:
In this case the normal map generator has got things wrong. It has interpreted the rust as holes when they are in fact at the same level as the surrounding metal. An even better example are the red and white stripes at either end. They are meant to be perfectly flat, rather than the red and white being at different levels.
This is where a new source image should be created:
Darker shades of grey are used to represent recessed parts of the object, and lighter areas are used to represent the parts that stick out (e.g. the three hinges on the right). I also showed the stickers, but was very subtle about it. It can also be helpful to soften the image slightly to eliminate jagged edges.
This is by no means a perfect source image. For example the edge of the door should be shown with a lighter shade of grey, and some of the panels have scratches that could be shown with a darker colour. However you would only need to add those extra details for objects that are right at the edge of the track.
Using Normal Maps to Add Detail
In the above examples the normal maps are intended to have the same scale as the diffuse maps. The normal map can be scaled to make a surface appear to have lots of high resolution bumps, even if the diffuse and normal maps are not particularly large images.
Here is a closeup of a track that just uses a diffuse texture (512x512 pixels):
If the material is set to have a normal map which repeats much more often than the track itself, the surface can be made to appear much more detailed than it really is:
The normal map itself is nothing fancy. It started out as random noise to which a normal map filter was applied:
The following settings are used for the normal map:
The result looks especially good when the angle of the sun is low: