When I plan a level based game, I usually write down all the level theme ideas I get.
Also, for the story based games, I make sketches of the map and plan the lore and stuff.
I also often mark things that need to be done and 'rank' them for how easy they are to be done, usually with smilies.
I use tons of graph paper while designing Metroidvania styled games; I've played far too many klik games in that style in which the level layout defied the laws of physics. (Metroid: The Egg Hunt was a great example of this) and it ends up getting the player totally lost.
Example of what I mean
A game I played had two halls (XXXX) on top of each other, the top one was much shorter than the bottom; but they both ended in the same 2 vertical shafts (H's). This obviously threw me WAY off, and the whole game was like this.
I tend to design my bosses on Paper too, but the final product is usually very different from the paper design.
I tend to do what Jay does, write variables and their meanings down on paper (1 = white, 2 = red etc). Also, when I haven't got access to a computer (which is most of the time these days) I will write down and draw ideas, level design, characters and ting.
I keep track of all my flags, values etc in a notepad doc. To plan games I usually use MoonEdit with someone else brainstorming with me, I don't normally plan levels on paper, because I can't draw on a grid and I find it tedious to follow a premade plan for a level.
Most of my personal planning (coding) is in me head though.
I don't plan things out fully, but I keep a record of all my wonderful ball-rocking concepts in case I ever decide to come back and use them. Sometimes I'll write everything I'd need to make the engine, and maybe a rough script, but that's it. If I'm planning on actually making something soon I usually won't bother writing anything down since it's all fresh in my mind anyway.
When it gets complicated, I end up keeping track of all the values and flags of the most common qualifier (generally Group.Good), as well as the meaning of the numbered qualifiers (like Group.0, as it's harder to form a mental connection to their uses than the ones with names and pictures).
However, I write this stuff directly into the game, in a few very tall comments.
For a project with a big, interconnecting map (well, for "Nothing", I guess), I mark all of the screens in a grid book so that they can connect in a reasonable manner (and make sense on the map).
I also write down what all the bytes mean in the level headers, as I'd never be able to remember that sort o' thing.
I'd write it down in a text file. Much easier to keep, find, backup, and I don't lose it like I'd lose a paper. My biggest project had about 3MB of text files, one of them a 25 page document explaining to me what all the formulas were for. Quite impressive, I even used it for college applications. I think I'll get back to work on it next year, along with upgrading the Click FAQ
Imagine the mess if all those pages on paper
Disclaimer: Any sarcasm in my posts will not be mentioned as that would ruin the purpose. It is assumed that the reader is intelligent enough to tell the difference between what is sarcasm and what is not.