Every specific group of blocks purposefully formed in Minecraft based on coding is a natural structure.
Hills
A randomly-generated hill.
Hills are randomly generated pieces of land in the map. Like stairs, hills are always traversable to their highest point by virtue of the algorithm which generates them; there is always a place on each level from where the next level can be accessed, meaning that the player can climb a hill one level at a time until they reach the top.
Cliffs
Some cliffs.
Cliffs are carved into hills, and sometimes have caves protruding into them. These caves contain the same blocks which one would find at the same layer in the hill they are carved out of. This may include Ores, Stone, Gravel, Sand, Sandstone and Dirt.
Floating "Islands"
It is rare to see a naturally occurring, large, floating "island." This one is on the pre-generated seed "Glacier"
Floating "islands" are structures that float in midair that are not connected to the to the ground, the sea, hills or cliffs. Floating "islands" are normally just random pieces of floating dirt found near cliffs, but on rare occasions they can be large, floating structures that even have springs and trees on them.
Oceans
An open Ocean with a couple islands in the distance.
Seas/oceans are huge bodies of water with every single water tile being a spring.
Lakes
A lake after the 1.2.6 update compared to the sea level. Since sometime around the Beta 1.2 update, these seem to be much more common than they were before.
A slightly rarer lake of lava after the 1.2.6 update. Since sometime around the Beta 1.2 update, these seem to be much more common than they were before.
A lake found at Bedrock, replacing the bedrock with water.
Lakes are geographical features of the map which occur where the level of the land drops below ocean level. Lakes are large bodies of water in which the player is able to swim, and are a large collection of water spring blocks.
Note: As of the 1.2.6 update, lakes can now be generated above sea level or inside caverns, and are small bodies of water surrounded simply by dirt, when in a winter biome, these small lakes are never frozen, unless possibly at sea level. These lakes can also be composed of lava; however, lakes of lava are more rare. It seems as of beta 1.2, lava lakes found at the surface will be surrounded by gravel, stone, and coal ore.
It is possible for lakes to generate at Bedrock, and the water will replace the bedrock. Lava lakes formed at Bedrock Level will have 1 meter thick stone beneath it. This stone can replace the bedrock at level zero, thus allowing a player to mine through into the void. It appears that when a lake is generated, it is generated after all existing terrain around it has formed.
This would explain oddities such as sugar supported trees, floating trees and sand, and why fires erupt around lava lakes.
Springs
A lava and water spring fall from a mountain side.
Springs are randomly generated blocks of either Lava or Water that act as a source of their respective material. While both can be found on the vertical side of stone blocks above the surface, lava springs are more often found underground beneath layer 32 in Caverns. Both of these sources can be collected and repositioned via the use of Buckets. When coming into contact, Water will turn Lava springs into Obsidian; however, if the Lava is not a spring, it will form only Cobblestone. Springs can only be found in Alpha, Beta, and Infdev. Fluids behave differently in older versions.
Trees
A variety of tree types.
Trees are the structures created both by the automatic generation of the map, and by players (they grow from saplings). They are built out of trunk blocks and leaves. When generated by the map, they are frequently found in groups, in the style of a forest. Trees can range from small trees, often found in groups, to large trees that may require multiple minutes to harvest. Recently in Beta 1.2 Birch trees and pine trees may be found, and in Beta 1.5 birch and pine saplings were introduced. Pine trees have so far mainly only been found in snow biomes. See the tree article for more information.
Caverns
A dark cave.
Caverns are caves and tunnels that are automatically generated under the ground in various places. They can be useful for several things, such as finding dungeons, and creating underground structures. Caverns are composed mostly of stone, but frequently contain gravel, dirt, bedrock, water, lava, and small amounts of ores, sand, and snow, (depending on your biome).
Mineral Veins
A Gold vein in Survival Test.
A Mineral Vein is a natural deposit of ores. Players can come across these veins in caverns, mines, or anywhere there is stone. Six ores can be found in the game, these include Coal, Iron, Gold, Redstone, Lapis Lazuli, and Diamond. When mined with a pickaxe, some ores (gold and iron) will drop an associated item or a block that needs to be smelted in order for it to be crafted into items or blocks. Others (Lapis Lazuli, coal, redstone and diamond) will drop items that can be used immediately.
Dungeons
A dungeon with a Mob Spawner in the center and two chests.
Dungeons are small, mostly underground, one-room spaces bordered by Moss Stone and typically contain chests with some satisfactory loot and a hostile Mob Spawner in the center, which guards the chests. Dungeons are often open to a cave, or more rarely even to the surface. Dungeons are the only place to find apples, saddles, Mob Spawners, Cocoa Beans and Moss Stone.
Unusual Structures
Unusual Structures are structures only generated by third-party generators and can come in the form of deserts, cities and hell-like lava wastelands. On Mac OS X, the inventory editor InvGrid has been known to make Minecraft start generating maps with abundant ores out in the open, despite not claiming any map-editing/generating capabilities.