There are many ways to approach procedural level design. For Torgar's Quest, I wanted randomly generated mine-like dungeons, so I went with the carving approach: starting with a map filled with "walls" from which you cut out the level.
The key to this approach is designing the carver object, the thing that cuts out rooms and corridors. You need to make sure, you don't get too close to the map edge, or you will have a hole in your level. You'll also want to decide when to turn in a new direction, and to do so at a good rate, thus avoiding long, unbroken corridors on one end of the spectrum and huge caverns on the other end. I spent a lot of time changing parameters to find an algorithm that generated the kind of map I wanted.
I realized, I would need more than one carver object in order to spawn off side corridors. At first I spawned these at different pre-determined coordinates and let them do their thing. However, this approach proved imperfect, because half the time one or more carvers would fail to connect with the others, so there was no path there, which in turn caused problems when spawning in things like the player and the level exit.
To fix this, I ended up creating a master carver, which would then spawn other sub-carvers from within its own path. These new carvers thereby start from somewhere along the main path and create forks in the map. The trickiest part then, was balancing when and where to spawn in the sub-carvers, in order to get a dungeon that felt right. Again, this came down to trial and error.
How I did it was based on time. The master carver runs for X seconds, and after a quarter of the time has elapsed, it spawns the first sub-carver, then again at half time, and finally again at three quarters. At full time, the master carver destroys all carvers and moves on to spawning in monsters, etc.
One challenge with this approach is time. The carvers need to crawl around and generate the map, but I did not want long load times for the player. A few seconds was fine, because it gave me a chance to display a new bit of the game story, but it had to be balanced. Initially it took too long for the maps to generate, so to fix this, I sped up the frame rate of the game while the map generated, thereby speeding up time in a way.
Once the carvers are done, the loading screen goes away and the action begins.
For more about Torgar's Quest, check out the website (where you can play the browser version, too).