it'd be easier to help you if you told us a bit more about the gameplay mechanics, instead of us tossing out random information that may, or may not help you.
The game I am making now is more or less a top down, real-time clone of Fallout 1. It will have the same style and kind of levels, junkyards filled with crappy cars, ruined cities with buildings, and deserts with nothing but rocks.
This project is just for me to learn how to generate levels so it isn't going to be as extensvie as Fallout so the levels don't need to be amazing. I am guessing I will need a different level generation algorithm for each type of level but I assume that if I learn how to make it for one, the rest shouldn't be that hard.
I just in game generate rooms on a plane and then use a star to interconnect these with each other. Seeing my game is cube based I actually do this for multiple levels and then afterwards generate the geometry, collision information and room items from that in memory map. this will only allow you to generate grid aligned paths or rooms but generally works fairly well for a find the exit type of game. I also do not care whether paths cross each other, I do have to mention.
What do you mean by "use a star to connect them"?