I'll personally set out a scratch drum track (MIDI, perfect timing, non exciting) then lay over an in time scratch guitar track. Scratch vocals too. Usually bass as well. All just enough to be able to get the feel of the song. I'll then track drum properly. Then add bass. Then add all the main guitar and keys etc parts. Then add vox. Then harmonies. Then all the extra little fills etc and solos. Then mix.
That applies to my personal songs. I like to get the foundations down first and build the song up. I like to be singing to a pretty full song when I do vocals so I sing it effectivly, but my guitars will be tracked with scratch vocals in place already so I know where they need to sit in the mix when I record so there is still place for the vocals when I record them properly.
Given the time, I'd probably want to take a similar route with recording a full band (though I've only done this once - at least a band with a drummer that is).
Take into consideration the band's personal preferences too. They might really NEED to play together to sound good - especially if they have limited recording experience. If they are seasoned pros already, chances are they will be quite comfortable playing to headphones.
Also the ego of the band may also mean they want to do it one way, but you just know it's not going to work as good as it can that way. I guess you need to listen to what they want, but also learn to tell them what needs to happen for the greater good of the song, sometimes. Further more, sometimes you need to actually trick them for the best performance. For example, some singers get exceedingly nervous when you say "ok, I'm recording now, make this take perfect!". You can sometimes get away with the line "I'll just get you to sing the song through a few times as a bit of a warm up and so I can get all the levels right. I won't be recording so don't worry if you screw up." Then actually record it. Little tricks like this could be very useful.
I guess the first thing to decide is if you're playing to a click track, or playing freely. If you're going click, I'd get a quick guitar and vox scratch track down that the drummer can play to. Record that, then work your way up the instruments as you feel appropriate. Otherwise, maybe just get drummer, one guitar and vox in the room so you can get the drum take, then build the rest of the song up from there.
There are really SO many options, and each one will suit bands and recording engineers better in different ways. So choose what works for you and the band!