At the simplest level, procedural content generation can be used to change the door codes and other individual puzzle elements to prevent a user from getting the information off of a game FAQ website or other source of information. But many game plots are little more than dependency graphs, which a sequence of actions must be performed in a particular order. Puzzles can be extended by making multiple parts of the dependency graph randomly placed (e.g. moving the key that opens the door to a random accessible location) or by changing the shape of the dependency graph completely.
Procedural techniques can be combined with Natural language processing to create plots and stories. But human imagination will create a plot out of a sequence of events without necessarily having an underlying plot. This may mean that the complexities of NLP may not be required for many games, as evidenced by the number of Day in the Life posts featured on roguelike newsgroups.
PCG Wiki References
Simple Procedural Quest Generation for Open-World Videogames - A graph based approach to procedural plot generation.
Procedural Puzzles And Plot Generation defined in The Death of the Level Designer.
Using strategy game AI to create plots - in the The Death of the Level Designer.
Roguelikes and OD&D - John Harris argues that pre-written narratives are not a requirement for storytelling.
Coding Self Contained Reusable Plots - Article and code examples (in Lua) on how to generate random plots.
Tips for Random Story Generation - Joe Hewitt author of GearHead on how to create random story lines.
Procedural Game Narrative - But Do Players Care identifies procedural generation of narrative as one of the top trends of 2008.
Procedural Storylines and Storytelling via AI High level description of how AI and PGC can be used to construct emergent storylines while using traditional story-telling concepts.