What you've noticed is the difference between a random number generator and a noise function. A random number generator spits out a different number each time you call it. A noise function takes some arguments - say, a map x and y - and spits out numbers with random-like statistical properties, but the same value for the same arguments every time, i.e. it is a proper mathematical function.
The two are very closely related. A noise function can simulate a random number generator, by passing in a different value each time - e.g. noise(1), noise(2), and so on. And a random number generator, dumped into a giant table, can act as a noise function. In both cases though, you're using the wrong tool for the job.
Minecraft in particularMinecraft in particular uses Perlin noise, a type of noise which is cheap to compute, and has a desirable property of being continuous in as many dimensions as you need - if you graph f(x) to f(x + 1), there won't be any sudden jumps. This makes it very useful for many things like texture modulation, volumetric clouds and gases, and terrain generation.
If you are looking for an implementation to start playing with, Ken Perlin's improved Perlin noise generator is one of the simplest implementations.