Dan Stahl in his interview on STOked this week suggested the best solution was to ensure you write your mission storyline out first, and get everything down on paper / Word before you start. This way you kow what assets, maps etc you're going to need in order to start developing missions.
I wouldn't recommend this for everyone, but I totally wing it. I start out with a concept for how I want the mission to be set up, who the major characters are and what the setting is. And then I just start editing without knowing how it will end.
Well as others have said, it's a personal preference. I do outlines about very general plot lines and how it should go or where it should be done on, but not specific things like dialog. And all of it is in my head, really, with few minor notes scribbled somewhere.
The emphasis I would add is sometimes the foundry gives you challenges that forces you to change your outline (as others also have said). Branching comes to mind the most when it comes to foundry challenges.
Anyway short answer: I tend to wing it if winging it means I only have a generic plot idea and progression in my head and I make that more wholesome once I interact with the tool.
If you're not a skilled writer, use a good word processing program first. There is no spell check in the Foundry, and you WILL be criticized for improper punctuation, spelling and grammar. It's in your best interest to know and overcome your own limitations prior to publishing a work that can be reviewed by others.
I haven't been using them, but I would agree with those who suggested it for people that aren't experienced at writing. Grammar and spelling seem to be one of the key nitpicking points (I'm guilty of this as well, of course; nothing turns you off of a mission faster than seeing "Go fight some Rmulanz!") so if that's not your strong point, use the technology available to help you.
Be careful, however. You don't want to get stuck like some of these people plotting detailed storylines that are completely impossible in the Foundry. Make sure you know what you can and can't do, and be flexible with the plan. I would recommend, if you haven't touched the Foundry before, to do some test missions on Tribble (So as not to waste your mission slots on Holodeck) to explore what's possible. Hands-on experience is better than a million how-to videos. Though, you might want to look at some of those too; kirkfat's videos can be quite informative for the more advanced techniques.
None of this is to say I'm going about this completely spontaneously, though. I have an idea of what I want before I even start the mission, but it's a flexible plan that can adjust to the limitations and possibilities. I also leave it open to new techniques that might arise in the future.
Upon reflection, I'd say have a rough plot outline. Then build the maps, which will give you a feel for what's possible. Then outline in a story editor only after you've built the maps, which will let you know what's possible.