Mesh Refinement

In a nutshell the best approach would try to minimize the data sent from RAM to the gpu or better from VRAM to gpu, and also minimize the number of transformed vertices.
Also it's important to notice that one implementation could perform better on specific drivers/hardware and worse on other drivers/hardware.
The worst approach would be to draw primitive by primitive, drawing using fans is a close one too. You could use separate triangle strips and draw everything in a loop for 1 to TERRAIN_WIDTH-1 = TERRAIN_WIDTH-1 passes, or use a big triangle strip.
When it comes to these things you only have one solution: TEST TEST TEST :).

use vertex arrays with glDrawElements() (assuming you're using openGL) This cuts down on the number of primitive draw calls dramatically as well as superfluous vertex/normal transforms.

Either triangle_strips concatenated with degenerate vertices

or index triangle lists and place them into VBOs

Thanks for your responses. I have been looking over several papers such as Lindstrom and older ones. I think I will try to do a full triangle strip as used by Lindstrom's paper and as some of you suggest. As you say, gpulove, test test test. I'll try and post something in my journal once I have something substantial. Thanks again!

Using the primitive restart extension its possible to batch multiple tri-strips or fans for maximum vertex cache reuse. NVIDIA has triangle rendering optimzation code available in their SDK.