Plan it, but you don't need to rigidly stick to the plan. Unless of course you're going for a shorter story, or have a word limit, in which case it's better to stick to the plan to avoid going over said limit. I plan the characters, major plot points in the story, stages, the beginning and end points, then I write it from there. If you rigidly stick to the plan, it makes the entire thing feel forced and it takes some of the enjoyment out of both reading and writing. But if you don't plan it at all, you can forget major plot points and go on for an insanely long amount of time on things you don't really need to.
So, plan it, but give yourself and the story room to add or change things, and allow it to grow.
P.P.P.P.P.P. Prior Planning Prevents Piss-Poor Performance. Very true. Planning reduces creating doing the same task two or three times over. You don't normally get in a vehicle with no knowledge of a destination or direction, doing so wastes time, energy and resources.
I loosely plan stories my stories, I outline certain events, connections or plot/character developments that I feel need to happen within chapters. I also research the hell out of anything that may/does pop up in. Planning and research are among my best friends when writing.
I have done free(unplanned) writing before. My writing goes nomadic without plot, direction or purpose; while it has the passion and feeling for the piece, it often lacks the clarity, direction and I often need to go back and rewrite it at least twice rather than rather than just one major rehashing and editing phase.
I've only written one short piece (it's a cross-over fan-fiction, and I'm sure I'll get flamed for that; but I wanted to figure out how to write characters that I already knew before trying to make up my own). I tried to plan out main points, like the entire first two chapters and the ending, but the rest ended up taking on a mind of its own, and I'm oddly proud of that.
Ooh. Difficult question. I'd say describe your story to someone before writing it and then write down whatever you told that person. Usually their questions (choose someone who will question you!) will help you figure out the fine details and telling them will let the story unfold on its own but you'll have that plan right before you write. Best thing to do is to figure out the key points in the story. A bit like the fixed points in Time and Space we constantly hear about in Doctor Who, the unchangeable things that must always happen, you should plan but the rest you should just let it flow however you please. It depends on the person but I find this method helps me the most.
I usually just have a geniral plan you know? Like lets say you want a war and all, how they get there and how things actually happen usually end up happing as I write because just in geniral I'm not a big planner and if I do I'm either disapointed because I couldn't get it exact or I lost interest already because the planning took to long or it took to long for me to get to the point where I wanted to write.