What happens when you reach the edge of the world?
From Notch's Tumblr:
First of all, let me clarify some things about the “infinite” maps: They’re not infinite, but there’s no hard limit either. It’ll just get buggier and buggier the further out you are. Terrain is generated, saved and loaded, and (kind of) rendered in chunks of 16*16*128 blocks. These chunks have an offset value that is a 32 bit integer roughly in the range negative two billion to positive two billion. If you go outside that range (about 25% of the distance from where you are now to the sun), loading and saving chunks will start overwriting old chunks. At a 16/th of that distance, things that use integers for block positions, such as using items and pathfinding, will start overflowing and acting weird.
Those are the two “hard” limits.
Most other things, like the terrain generation seeds and entity locations use 64 bit doubles for locations, and they do much subtler things. For example, at extreme distances, the player may move slower than near the center of the world, due to rounding errors (the position has a huge mantissa, the movement delta has a tiny, so it gets cut off faster). The terrain generator can also start generating weird structures, such as huge blocks of solid material, but I haven’t seen this lately nor examined exactly what behavior causes it to happen. One major problem at long distances is that the physics starts bugging out, so the player can randomly fall into ground blocks or get stuck while walking along a wall.
Many of these problems can be solved by changing the math into a local model centered around the player so the numbers all have vaguely the same magnitude. For rendering, Minecraft already uses local coordinates within the block and offset the block position relative to the player to give the impression of the player moving. This is mostly due to OpengGL using 32 bit floats for positions, but also because the rounding errors are extremely visible when displayed on a screen.
We’re probably not going to fix these bugs until it becomes common for players to experience them while playing legitimately. My gut feeling is that nobody ever has so far, and nobody will. Walking that far will take a very long time. Besides, the bugs add mystery and charisma to the Far Lands.
As of Beta 1.8 [source]:
In beta 1.8 the strange terrain may be gone, but some of the effects aren't. After X/Z ±30,000,000 the world will start generating fake chunks. Going into the fake chunks will result in falling into the Void, and, subsequently, the player's death. If flying is used, going about 34 blocks out of the limit will cause you to be stuck, being able to use your inventory and look around, but not to move. Also, the clouds will act strangely, moving at abnormally high speeds. Reloading the save should fix the clouds, but the position glitch will still be present. Also, at excessive X/Z positions, particles (rain, water, snow, etc.) fail to appear staggered, instead forming rows of flat "panes". The Far Lands do not lag in 1.8. in 1.0.0 the fire of torches will be in/on a block next to it, instead of on the torch. In 1.0.0 explosion clouds look abnormally big. Piston heads will disappears when the block is activated and will have the same effect as sand does when falling (then disappears). Paintings can be placed over paintings near the far lands. Also, the floating book in the enchantment table seems to behave abnormally when a player is moving near it. Redstone appears either extremely distorted, with stretched graphics, it can appear misplaced, or it can appear completely invisible, but the highlight box still appears indicating where redstone is placed. Cauldrons, when looked from the inside, one of the sides is translucent, and the graphics for that side appear one block away from the cauldron on the opposite side of where the texture is missing from. Highlight box for cake fails to appear correctly. Flames from a monster spawner only appear on one side of the block. The graphic for end portal block fail to appear correctly.
A few patches ago the world was practically infinite (couple of million kilometers) but with the later updates problems occur closer to the 0 point (around 8000 kilometers)
As seen in the video (not mine) bounding boxes will be located differently from the cubes themselves, movement stutters and various other problems come up (going even further renders the game completely unplayable).
This still leaves you with around (2*8000)*(2*8000) = 256000000 square kilometers of playable surfaces area (the distances only matter on 1 axes for the most part so its a roughly square surface, its also times two cause you can go 8000 kilometers both north and south)
Notch himself wrote a blog post about Minecraft's world generation.
Short answer: The maps are infinite (until your hard drive fills up), but will become buggier the bigger they are.
Long answer:
How infinite is it?
First of all, let me clarify some things about the “infinite” maps: They’re not infinite, but there’s no hard limit either. It’ll just get buggier and buggier the further out you are. Terrain is generated, saved and loaded, and (kind of) rendered in chunks of 16*16*128 blocks. These chunks have an offset value that is a 32 bit integer roughly in the range negative two billion to positive two billion. If you go outside that range (about 25% of the distance from where you are now to the sun), loading and saving chunks will start overwriting old chunks. At a 16/th of that distance, things that use integers for block positions, such as using items and pathfinding, will start overflowing and acting weird.
Those are the two “hard” limits.
Most other things, like the terrain generation seeds and entity locations use 64 bit doubles for locations, and they do much subtler things. For example, at extreme distances, the player may move slower than near the center of the world, due to rounding errors (the position has a huge mantissa, the movement delta has a tiny, so it gets cut off faster). The terrain generator can also start generating weird structures, such as huge blocks of solid material, but I haven’t seen this lately nor examined exactly what behavior causes it to happen. One major problem at long distances is that the physics starts bugging out, so the player can randomly fall into ground blocks or get stuck while walking along a wall. - Notch
The map is pretty much infinite. The Far Lands do get quite weird over time, because, as Notch stated, problems in the map generator produce some weird effects.
As close as 500,000 blocks away from your spawn point, the frame rate starts to slow down. As you get further and further away, the framerate keeps on slowing down to the point where you cannot move at all. Then Minecraft crashes.
The point in which the Far Lands really begin, however, is at X/Z 12,550,821. The terrain generator starts going crazy, producing amazingly tall and smooth floating structures that keep on going to infinity. The Far Lands are monster magnets, because the spaces between one structure and another are pitch black, so they are able to spawn.
At X/Z 32,000,000, the terrain generator goes out of control. The structures don't change, however now there is no lighting, trees, monsters or animals. You will have to use a mod to fly now, because now the block positioning system is out of control too. If you are not flying, you will fall through the blocks into the Void (yes, even the Bedrock goes crazy). While you are flying, try to break a block at the top of the Far Lands. First you will find out that it is very hard to do so. Second, when you have done it, the hole in the block shakes from side to side.
At X/Z of ±2,147,483,648, positions of items, mob pathfinding and other things using 32-bit integers will overflow and act weird, usually resulting in Minecraft crashing.
Finally, at the hard limit which is at about X/Z ±34,359,738,368 (if you convert that to meters, is is one-quarter of the way from the Earth to the Sun), blocks and chunks will simply stop generating.
Sources:
http://www.minecraftwiki.net/wiki/Far_Lands