I think I better understand what you are asking now.
Noise is not random - it's random-looking but is completely based on a mathematical formula and is repeatable. All the information is encoded in the formula. This means that you can have a formula that potentially covers an infinite area, and just use the formula on the coordinates of the area you need. When you need an adjacent area, you just re-use the formula on the new coordinates, and since the formula yields continuous values, the areas will join seamlessly.
Here's a simplified example, using sine instead of perlin noise for the height generation, and imagining the world is infinite in the X axis but only 1 unit high in the Y and Z axes.
height(x,y) = sin(x/20)
The game starts, and we generate heights for the nearby area, ie. (0,0) to (9,0):
[0.0, 0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.34, 0.39, 0.43]
We have a hill, rising up towards the right. Let's say we walk to the end of it and need to generate the values from (10,0 to 19,0) now:
[0.48, 0.52, 0.56, 0.61, 0.64, 0.68, 0.72, 0.75, 0.78, 0.81]
Notice how the hill keeps rising steadily, and that the value at (10,0) follows on nicely from the one at (9,0). This is because the sine function is continuous, which basically means that if you feed it 2 adjacent numbers in, you'll get 2 adjacent results out - for a certain definition of adjacent. So if you use your world coordinates as the parameters to the function that defines your world, you will get a continuous landscape that fits together no matter how much or little of it you generate at once. When you generate new parts, they will flow on from the existing parts automatically, because the heights are already pre-determined.
If the world isn't going to change, you don't even need to store anything, since you can calculate exactly what the height is at any given point from the formula. Obviously with something like Minecraft the world is totally deformable so you just save each chunk as you create it. Given that there is a high degree of coherence between adjacent chunks (ie. if 1 block is grass, it's more likely than not that the block next to it will be grass too) you can compress the data very efficiently - run length encoding would work well, but then so would almost any standard compression algorithm.
Whereas I have talked about height as the most obvious value, you can use the same system to generate any characteristic you want. Use a mathematical function with continuous properties and where the inputs are your world coordinates and that can decide the presence of landmarks, mineral deposits, spawn points, whatever you like. (Obviously the values in one formula may affect another - no point placing a coal deposit in mid-air, so you generate the world height map and then only calculate coal possibilities for the blocks that are far enough below ground.)