HereForTheBeer: I'm not sure, actually. I only took notice of people's response in the release threads and that had me wondering about it.
Maybe someone with good insight could explain the, I dunno, 'levels' of PG. As mentioned above, some use it at quest level while others use it to create the entire gameworld a la the Civilization games. And I suppose there is a ton of variation in-between.
And where does randomization fit in? Also as mentioned above, true randomization likely wouldn't work with many games as it would create unwinnable dead ends, a world filled with one-hex islands, etc.
There are all sorts of things that can be procedurally generated; the crowds of bystanders in games like Assassins Creed or GTA, whole worlds and levels (or universes) in RTS and 4X games or quests or enemy placement (or a combination of all of the above)
As for randomization, procedural content will hardly ever be truly random (one, because true randomness is quite difficult to achieve and two, because true randomness would more often than not lead to broken levels) but will instead be governed by a set of rules that can lead to very random content (the levels in most roguelikes or the maps in an RTS) or just small randomised elements in an otherwise designed world (like randomly placing vegetation or trees).
It doesn't even need to be random at all as the algorithms used can be made to recreate the same world each time (which is basically just a fixed input as opposed to a seed generated fresh each time) and in that case it is a way of creating very large and detailed worlds without taking up a huge amount of disk space.
Bookwyrm627: Arena and Daggerfall might be, but I'm certain that Morrowind and Oblivion are not, and I'm pretty sure Skyrim isn't either.
Nope, I'm fairly sure Oblivion and Skyrim are. They're just not random. They generate the terrain based on algorithms, it's not saved and loaded from disk, it's loaded each time from a seed.