A heightmap is an two-dimensional array of values (typically 8-bit values) which specify heights at different points on a surface, typically as part of a terrain to be rendered by a computer.
Normally created and visualised as a monochrome image.
The problems with storing terrain using this method is that there is no way to represent overhangs, and for large pieces of terrain there is either a lack of detail in the heightmap or a problem with storing large amounts of data.
There are various programs available for generating them, including TerraGen and Bryce 3D.