How do level seeds work?

Computers are deterministic machines, incapable as such of non-deterministic (= random) behavior. What they can do is use complex math to simulate random behavior: this gives pseudo-random numbers.

For example, when I run Python 3 for Windows 7 I get:

>>> import random
>>> random.seed(1) #I set the seed to a fixed value...
>>> random.random() #and ask for 3 "random" numbers
0.13436424411240122
>>> random.random()
0.8474337369372327
>>> random.random()
0.763774618976614

I then connect to an Ubuntu 11.04 machine with Python 2, and get:

>>> import random
>>> random.seed(1) #I set again the seed to the previous fixed value
>>> random.random() #and ask again for 3 "random" numbers
0.13436424411240122
>>> random.random() #...doesn't look very random, does it?
0.8474337369372327
>>> random.random()
0.763774618976614

So, the same pseudo-random engine will always give the same numbers in the same order. This doesn't imply the game actually uses the same numbers in the same way, however, as yx_ insightfully thought. However, the game could be written in a way to ensure this; for example, one could derive from each seed (say, "foo") a different seed per each block (say, "foo@1@2" to determine the chunk 1,2). How can we tell how this is done?

There's only one way to know!

I used the seed "Mersenne" to create two worlds, a world A and a world B.

In world A I spawned in world A at (262.5, -280.5); I attempted to move in the direction I spawned in as straight as possible for 500 units, then back for a thousand. This is what I got.

In world B I spawned in (+259.5, -276,5), just to make things easier. I attempted to move in the direction opposite to the one I spawned in for 500 units, then back for a thousand; in short, I travelled back and forth on the same 1.5 km, just in a different order. This is what I got.

(Keep in mind that, as I explored, I removed blocks here and there for navigational purposes.)

This results are shockingly identical. I say shockingly because I certainly had the impression the two worlds were quite similar... but not quite the same.

Indeed, if we zoom on the spawn point, we can see some differences... but it is mainly only about trees. The underground area is not pictured, and identical.

In short: the seed system is almost perfect and the same seed will give you two worlds that are almost identical to each other. I haven't tried the nether, but I have no reason to believe it would behave differently.

The seed in Minecraft is used as a random seed, i.e. it causes the terrain generator to produce random terrain, but in a repeatable way. Using the same seed will result in identical terrain, for as far as you walk, right down to the flowers, and the nether.

Your spawn point may not be identical, however.

There are around 18 quintillion (18,000,000,000,000,000,000) different possible seeds.

The seeds for a map in minecraft is used inside a Pseudo Random Generator.

A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state.