The answer depends on the kind of terrain features you want.
Either case, my first thought was to use Perlin noise, but that may be because that's what I used on my previous project which was essentially a procedural terrain generator.
If you don't need to have overhangs or caves generated, you can use a 2D perlin noise function over a flat grid. Perlin noise usually returns a [-1, 1] value, which you can then scale and transform to your needs to determine how you set mountains, plains, lakes, etc. There's a noise library and corresponding tutorial here: http://libnoise.sourceforge.net/tutorials/tutorial4.html - but that's just one of the many, just google "perlin noise terrain", you'll get a lot of results.
A standard method to make continuous terrain as your move around is to use a quad-tree. There's a nice visual representation of quad trees in action here:
- but again, it's far from the only tutorial/demo online, you should be able to find dozens of these online.
Advantages of heightmap
- Fast (samples only grow quadratically as you increase visible terrain)
- Easier to make smooth transitions - there's not so hard to learn and well described known ways to have different Level Of Detail quadtrees blend together without holes in them
- No Caves or Overhangs possible
Another way, which I used for my old project, is to take 3D perlin noise, and generate terrain from that. This involves sampling a perlin noise function over a 3d space (not just a flat 2d grid as with heightmaps). It gives you a bit more control, and also a lot more variation too, since you can have bumps, overhangs, caves and the likes easily. The samples from the 3d noise function can be used to construct a mesh using the Marching Cubes algorithm.
The article I used when I was starting this was this: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html
This describes terrain on the GPU, which has advantages, but it's also doable entirely on the CPU as well, though slower. Using libnoise and smart construction of the marching cubes, I had some fairly good results (look at my journal here on gamedev for some of them). The problems with using 3d noise is speed and the difficulty in producing meshes at multiple levels of detail that go together without holes inbetween them. The GPU Gems site suggests a way to overcome this, however I think their method is inefficient as it draws the same terrain multiple times at different LOD.
- Caves, Overhangs, more detail
- Slower, number of samples grows cubically in worst case, unless you impose artificial limits to height.
- Harder to produce smooth transitions between different LOD terrain meshes - there's a lot of approaches I've read, none solve this perfectly for me.
Both of the above methods can give you incredibly fine detail up-close, if set up correctly.
This is just terrain generation using perlin noise, which is what I'm familiar with. There are other methods to do this, which involve more numeric approach (as opposed to analytical functions), where you generate simple terrain and iterate over it, deforming it with each pass, to produce the desired features. This is again done through automated functions, and it can give some more control in what you want to generate and where, however it won't be able to generate extreme closeup details by itself. I'm also not sure how this approach would work with different LOD since it usually requires a full-resolution terrain to work properly. I only have a passing familiarity with these methods, I'm sure someone else will describe this better.