Such things usually consist of a heightmap (a grayscale image where the brightness corrsponds to the height in the terrain) and a texture on top. The shadows are precomputed based on the heightmap and the sun position.
Put a skye dome at the horizont and some fogging, your done.
The technique is often referred as Raycasting, or 2.5D. This is the very same technique used in many voxel scene demo or in the Doom game serie. Probaly NemacIV as well.
Each vertical line on the screen is a trace through the terrain, starting from the cameras 2D coordinates.
Using Z-Buffering, it is easily possible to place 2D sprites in the terrain (like the game sprite someone spotted in some pics above).
The technique pretty simple and nothing groundbreaking, every skilled programmer can do that in a week or so. The nice look comes from the nice artwork.
I use perlin noise to generate the "fractals".
The "man-made" stuff in painted in ArtEffect.
For the perlin noise, I have written a tool called "PerlinFX". You can generate heightmaps as well as textures.
http://www.hd-rec.de/HD-Rec/index.php?site=contributionsExamples: