It's time for me to talk about the core of any constructive procedural game (Minecraft, Terraria, etc.),
the actual procedural construction! The world nobody has ever seen before that seems to emerge from nothing.
It's really not dark magic or hidden secrets of Computer Science, the key is always FRACTALS.
Fractals are any complex pattern that has the same appearance at any scale.
Take a look at a map of our planet and you can see a similar random pattern if you zoom in on a chain of islands or the coastlines.
The real world isn't actually built on fractals- fractals are a mathamatical concept-
but you can create something that looks a lot like it yet is different using them.

Being more practical, world generation in these kinds of games is often done in two steps.
The first step has always been identical, tried and true across many of these games.
A Perlin Noise topology is created using a 2D pattern (for 3D cube games) or a 1D pattern (for 2D side-scrolling games) which specifies height of the land.
Perlin Noise is just levels of noise added on top of one another with each "smaller" "higher resolution" layer being added that is a factor weaker than the last.
The result is this sort of "cloudy" pattern which looks naturally made.
Additional topologies can be created and overlayed to add additional mixtures of features (roughness, forest density, biomes, etc.).

Where these games diverge is the generation of the actual land based on this topology. One example is if you generate a 3D voxel map using Perlin Noise and pick a threshold
between land and air, you'll get nice random volumes of land. Clamp this to your heightmap and adjust for the topology to get a very Minecraft-like world.
If you actually do this you may notice lots of noise and floating cubes. One quick and dirty fix Notch once used was to not generate all levels of the Perlin Noise map,
this resulted in smoother terrain that could be rough in some places, flat in others, and wouldn't have too much noise in it.

Sometimes you could more explicitly carve out caves and add features using primitive "brush" shapes. Your program would decide to create caves directly and could
carve fat wavy lines of air into the ground. It could add hills using random phases and amplitudes of cosines or with frequency modulation synthesis.
And of course, it can dot the underground with little ore pockets for the player to find.

Eventually you may decide to generate existing built human-made like structures, especially dungeons.
This could be done in a classic mystery dungeon style by assembling patterns and choosing randomly the next piece to attach based on the previous pieces.
It is this second stage where the games begin to differ and get their unique feel from.

LandTraveller uses layers of fractal noise to create these world map samples with their biomes, oceans, etc.
If you look very very closely, you can see little purple pixel dots where landmarks, dungeons, portals, additional features, etc.
may or may not be generated. This simple idea can create parts of the world the player would have fun finding and exploring.
The world maps here are of fixed size, so it is possible to try and complete everything in a game world.
Even if you manage to do that, the next generated world could be completely different from the last adding lots of replay value.
You could challenge another world with a new character or use your existing built-up one.


To view sample world maps:

http://landtraveller.com/sampletop1.png
http://landtraveller.com/sampletop2.png