Minecraft at a minimum uses a variant of perlin noise for the terrain generation.

Also, while it doesn't have the replay value found in the Minecraft sandbox, Starbound procedurally generates not only the map/terrain but also the mobs.

http://en.wikipedia.org/wiki/Starbound