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.
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, Perlin 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.
PCG Wiki References
The following images on Flickr have been generated using Height maps: