Pen and paper first is my approach. I like to do workflows and ideas on pen & paper with lots of bullet points and rewrites. I go off to a secluded, quiet area and turn off the cell phone/computer and then I just start writing in long hand what my idea(s) is. After that, I start thinking about what features to add in - I'm not really being discriminate yet; any idea will do - and write those down.
Once I've done the initial brain dump, it's time to tighten it up (and more coffee, please). I re-write it all trying to make it shorter and more explainable to someone else. This inevitably leads me to other ideas and again I just brain dump - no worrying about shortening it or explaining it at this stage.
Okay - take three is tightening it up further and segregating into bucket "A" (must implement in beta), "B" (must be present in version 1.0), and then I put the rest for later. I write up the summary in 3-4 sentences max.
Done with that part of the planning stage - now it's time for workflows. I figure out the major consumers - who's going to use the product? I then create a page for each of them that describes, in minor detail, their usage of the product.
Once I have that done, I then re-write it all and tighten it up which inevitably leads to more ideas... And then I tighten it up once more.
Once I'm done with the paper part (usually several days), now it's time to prepare a mockup of the product's main features using a graphics editor. Once I have designed these, then it's time to start building.
When I build, I like to build the prototype first in terms of look/feel and then add the guts later. I'm very concerned with code maintenance here (assuming you are programming) as I know that I will rewrite this 10x in the next month and 3x in the next year. Take your time - you can make mistakes here that will be felt for years.
Good luck!