The Void, found on the bottom of the map.
The Void is below the grey horizon, which is in turn below the sky.
The Void above the top layer of bedrock in the Nether
The Void is the empty space under each map. It can be seen through gaps in the lowest layer of Bedrock. These gaps only exist on regions of a map that were generated prior to the Halloween Update.
This space is the blue in color, and will change from light to dark depending on the time of day. During the day, it will also give off light like a torch. Falling into the Void will cause the player's health to rapidly decrease by 2 hearts about as rapidly as the player is hurt standing in lava, killing them in at most five hits, or about 2.5 seconds. After respawning, the player will have lost all held items with no way to recover them, as they have fallen out of the map.
Items, falling Sand and Gravel, and mobs will disappear if they fall into the Void. Water and Lava will appear to flow into it, but will not actually spread and form beneath the lowest layer. This effectively prevents players from descending into the Void safely via swimming. Blocks cannot be built on the underside of the Bedrock layer.