The simplest (though not necessarily most efficient in terms of speed or memory) is to generate two triangles for each quad and upload that to the GPU as a single VBO.
As you pointed out though this till means you essentially have three times the amount of data compared to the height-map itself. (An index buffer should be used so there are no duplicate vertices).
This is a good tutorial IMHO covering this approach: http://3dgep.com/?p=1116
Another method is to use triangle-strips and link each row of the terrain using degenerate triangles so that you only have one draw call. Still has the memory overhead though.
Depending on how proficient you are with OpenGL (and how modern your graphics card is) you could look at tesselation shaders which get around the above problems by using the height-map 'texture' directly:
http://codeflow.org/entries/2010/nov/07/opengl-4-tessellation/