A height map is a bump map, which is essentially a greyscale version of a texture where the higher a pixel is in relation to its surroundings, the brighter it is. So bricks would look like this:

The recessed parts are dark compared to the raised bricks. Typically, mid-grey is considered to be the middle, with anything darker being recessed, and anything lighter extruded.
Now with the heightmap, you can make use of Blackhole's parallax mapping. Parallax mapping, as the name implies creates visual parllax error in a surface. It does this by shifting the map around according to how high each pixel is (heightmap) and the viewing angle. So using the classic example of an analog clockface, if the heightmap indicated that a clock hand was raised above the surface of the clock and the clock was being viewed from the side, parallax mapping would shift the pixels of the clock hand away from the camera, so that it would appear to be in the same position it would if it were _actually_ raised above the surface. This would change depending on where you were viewing it from, so viewing it from the other side would shift it over in the opposite direction.
Anyway, heightmaps are typically created by hand. Though you can generate a height map from a normal map, normally you would develop the heightmap from your base texture in the same way you'd make the shinemap, and then generate the normal map from the height map. If you have BIG deep or tall features on your normal map, then you should use the heightmap as well to make use of the parallax mapping. In all other cases, you should just use a normal map, or none at all if you can get away with it. (One less texture to store)