Periodically you should re-draw your maps. They should differ subtly over time; a hallway will move or a room change in dimensions. The effect surreal: the rooms are no longer quite trustworthy, and the underworld is a fundamentally stranger place. This is an effect that should be used more often as the players explore the lower levels of the dungeon.
Less subtly, the denizens of your underworld may be remodeling. The infamous "Greyhawk Construction Company" signs blocked routes in Castle Greyhawk where Gary Gygax was still working on the level in question. Depending on the tone of your dungeon, that may not work, but having clues of dungeon denizens doing heavy digging can give players future points for reference and later delving.
All of this is another good argument for creating your own megadungeon. If you start with Stonehell, for instance, and you keep this to heart - after a while your Stonehell shouldn't look like the original. This is somewhat easier when you've drawn the original maps as well as the revisions.
The most important rule of restocking is: don't punish players for making progress. A dungeon level shouldn't get harder with each successive raid into it. There are two points for this: first, don't increase the effective dungeon level when restocking, and second, don't restock all of the rooms. A megadungeon populated according to OD&D or Moldvay should already have a bit of breathing room, and getting to already-explored boundaries should generally become quicker than the initial foray. That's a reward for good play.
At least some restocking should be simple and logical. If the PCs leave a stack of dead goblin bodies, there is something in the dungeon that will want to eat them. You can pick from the "clean-up crew" or add something an animal (giant or otherwise) that makes a nest out of goblin bones. A room might be converted for use by a previously wandering monster. Or, if you want to make the PCs much more careful about disposal of enemy corpses, they might now wander into a room full of zombie goblins.
Then there are the dynamic parts of restocking. What other factions are interested in the territory that the goblins used to hold? This could be a guardpost or the site of a new trap, as the other dungeon dwellers seek to find out who has been killing the goblins. Factions can come from other areas of the dungeon, or you could have a wilderness group start to move into the newly vacated area.
Dungeon restocking, as a general question, is a question of time. This is a big part of why Gary Gygax made his infamous statement in the 1e DMG about "strict time records." (The other part was related to the open table game concept.) The longer the PCs spend away from the dungeon, the more time that the denizens have to move into and reinforce areas that the PCs had previously emptied.
If a faction is damaged, but not wiped out, it can of course dig in and lay traps for these new threats. Whatever was killed may also have had a predator/prey relationship, such as when the PCs kill the giant lizard that ate the giant rats, there might be a sudden overpopulation problem. Or, when they killed off the nest of giant rats, the lizard is now wandering around eating goblins (or of course adventurers when they're handy).
The central idea with the living dungeon is that the PCs' actions have meaningful consequences. Sure, a character who stops in once doesn't see that, but for the dungeon to stay fresh and keep being interesting instead of just a slog, characters should be able to see it change around them. This is particularly important when making sure that PC actions leave a stamp on the world. I like how Stonehell encourages players to leave their names; it's a great tradition. But a great dungeon delver should have some personal impact.
The last type of restocking I want to cover here is the idea that the dungeon has some mystical underworld connection to what is inside of it. Maybe the dungeon seeks a kind of equilibrium in the creatures that inhabit it, and the PCs have disturbed that. There will be ripples. This can become more dramatic once they are removing large numbers of magic items or if they kill a dragon or similarly magical inhabitant of the dungeon. Maybe the dungeon grows or attracts more monsters; maybe it changes organically to attract new inhabitants. Above all it should get weirder: portals should stay open too long, or magical energies find their way in, or the water elemental you summoned six months ago had babies.
So, don't forget to restock your dungeon. In putting this together I realized I also had some points on the wandering monster that I want to talk about, which will be the next post.
