On the Geniant blog, T.Scott Stromberg exposes his craft of wireframe sketching. I also spend most of my ideation time sketching. It's lovely to see other people's methods for getting ideas down. I love Stromberg's comments and comic book style.
This might sound kind of pathetic, but seeing the pens and paper he uses is the kind of thing I really geek out on. I love that he's pimping out the Behance dot grid pads. A designer gave me a pad of that stuff recently after I got him a leatherette Rhodia 3x4 case. I carry one of those with me everywhere with a Pentel .7mm pencil. When I sit down to work on a large project, though, I use the Tufte 11x17 graph paper, with the Pentel and a Micron. I have to agree with his method of inking the sketches. I've gotten accustomed to doing that when I have to scan sketches to send to people, and tracing is something I'm used to doing from comic book sketching.
Another option to consider in a pinch, or if you can't stand to buy expensive paper, is to print your own graph paper with the graph paper pdf generator or download grid and graph paper from McGraw Higher Ed. Will do paper up to 11 x 17 and lets you specify line weight and color.
Thanks, Soul Soup, for the link to Stromberg's article.