It is generally best to have a visual blueprint up or at least the structure sketched up so you have something to work off of. I don’t believe that it is ever a good idea to just start without some kind of starting point.
On topic, I usually skip the Fireworks/Photoshop part (when I can), mostly because I suck as hell with those tools, but I always spend a decent amount of time on paper. Paper is good to sketch things, people often seem to forget this.
@paulie_d Oops. I thought you were implying something else. I agree that Fireworks is strictly suited for the web. However, I still prefer PS and AI as a hybrid because you never know when you’ll need it for print work (personal business cards, etc).