Quote: "Does a normal map store height information, or purely RGB colors?"
Neither, the pixels (colors) of a normal map depict surface angles (normals).
The shader's lighting calculations then use that information decide how much light will have fallen onto each point of the object based on the distance and angle between the light and the surface.
Displacement, Parallax, and Relief mapping shaders use height information to cause a surface to actually look pitted, but they each come with their own issues. Parallax mapping has a weird "texture swimming" effect when the camera is allowed to get too close. Relief mapping can look really "choppy" from steep angles (from the way it is drawn in layers). Normal mapping is the fastest of the bunch, and looks good from all angles.
They are all possible from within DX9, and have been done many times. Some awesome demos can be found on Evolved's site:
http://www.evolved-software.com/.
Quote: "How do you match up a normal map to a texture map so that they fit right with complex and subtle textures, such as sand on a beach?"
The shader would use the same UV coordinates for each texture, as each texture should be layed out identically.
Quote: "If the normal maps don't store height information, do the textures themselves?"
Some shaders use the normal map's alpha channel for height information, while others use an additional heightmap texture. It really is up to whoever coded the shader.
