There are as many ways to go about procedural generation as there are potential random variable outcomes, it depends on the parameters and needs of the user. There's a pretty extensive resource thread on the subject on tigsource here that people may find interesting.
I also found the .kkrieger demo really facinating for what they managed to accomplish.