Permadeath is where dying forces you to completely restart the game, as opposed to returning to a save point. With procedurally generated levels, permadeath is less of a problem as it is unlikely you will repeat the same game space as you played in the previous game. Why reload the same level to exhaustion when endless others exist?
PCG Wiki References
Permadeath - Article on permadeath in roguelikes on Ascii Dreams. Also resyndicated as Analysis: The Game Design Lessons of Permadeath on Gamasutra.
Infinite Caves, Infinite Stories - Article on Spelunky featuring discussion on permadeath.
Permanent death - Wikipedia article.
Permadeath - Article on Rogue Basin wiki.