A height map is a system that stores terrain by representing height (Z) as a function of horizontal position (X,Y), that is Z = f(X,Y). In other words, every place has exactly one altitude, a height map cannot directly represent caves or overhangs.
A height map isn't so much of a PCG technique, as much as it is a data structure that can be used as output or input to a PCG algorithm. For example, Simplex Noise can be output as a height map, turning a 2D grid of values into a 3D surface. Any Texture Synthesis technique can be used to generate terrain by mapping the color of each pixel to altitude.
Code Example
Shamus Young has a series of articles on an engine for displaying height maps. The first page gives some background, including some of the limitations of height maps.
PCG Wiki References
External Links
Eskil Steenberg describes techniques he uses to make Love, including the height map (look under the "Engines" heading).
Height Maps - Wikipedia article on Height maps.
Flickr Stream
The following images on Flickr have been generated using Height maps:
