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_yx_ insightfully thoughtthought. 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.
