Procedural generation works on the idea that you know what you want to create and how it is created but you leave out the details. Think of a set of sliders for color, size, roundness / sharpness, amplitude and such aspects. You don't want to define every aspect of the result by hand. You want to outline a general idea of what you'd like and won't like to see, color sets, surface smoothness, and such.
This obviously defines the world in it's virginal state. You are saving hard drive and memory space because you aren't storing a lot of detail. You let the details get randomized with a predetermined seed which means, you don't know what will happen but it will happen again and again every time (like perlin noise from a seed), in fact, the creator says the worlds are created by noise that uses a seed to repeat the same results. It is all build on the notion that you have the functionality to build a planet using a set of values to define it's properties first and then you let the algorithm, randomly pick these values. The universe itself is built on the concept of randomly picking far enough but not too far spots to place planets.
To store player modifications, you normally wouldn't want to store the entire mesh with the modifications applied to it (i.e. storing the result) as that would be space consuming, what you normally would do is store the actions the user took. Think Command Oriented Architecture. Then when someones else approaches that area, you need to "replay" these actions as you generate the mesh. This is where things get challenging. If the player has a lot of power to modify things in the world, it could require a lot of processing power to replay these actions. This is why I think something like digging tunnels (like it's done in Minecraft) would be very hard to accomplish if you don't store the results. It is entirely possible though.
Also think of more complicated aspects, a player kills a bunch of animals. Now time passes by and the world changes because time affects it, would the players actions affect the world? In a sense probably no. Killing a hundred deer will probably not cut down on deer population (as we have come to expect from MMO) as the world will be restored to it's virginal state and be repopulated according to the seed of time and space. Unless of course, the server stores the hunting activity and takes it into account when respawning new creatures.
A lot of interesting effects of player activity that don't relate to game mechanics and have to do more with simulation are lost if everything is generated on the spot. How does cutting down the herbavor population affect the carnivor population? How does it affect the plants in the area? But I digress.
