If you're a puzzler you're part of a club and as with all clubs there are insiders and there are outsiders. A sure way to spot outsiders is the tell-tale question they ask upon learning you have the addiction: pen or pencil? There is an answer, of course, and that answer is ballpoint pen.
What novices don't know is that counter intuitively the best way to "pencil in" answers is to use a pen. You can write guesses very lightly, scribble in better ideas a little darker, and then press down when you're sure of the letters. I use a continuum of pen pressure to indicate my internal confidence and it helps me quickly decide what the right tradeoffs are when arbitrating contradictory possible answers. Pencils don't work nearly as well and once you start trying to use the eraser the page quickly becomes a mess.
The larger question is what are the best tools for physically working out the solution? If you solve while riding the subway to work scratching onto the folded (now-not-quite-so) broadsheet, all you need is your trusty click pen. If you prefer solving at your computer, there are more options.
Most newspaper sites have Java versions available. These are almost always disastrous. The user interface is clunky but worse, should you inadvertently close the page which is easy to do in a browser for many non-intuitive reasons, you lose all your work.
Fortunately for NYT fans, that web site also publishes in a nice open format called Across Lite. It's an excellent little native application meaning it's not constrained by browser limitations. The timer works well and sometimes the guys at the Times set it up correctly so it starts automatically when you open the puzzle. You can save partial solutions and best of all, the answers are revealed through a 4 digit code that is published 24 hours after the puzzle. No matter how tempted you are, you have to wait if you're working on the latest. If you completely screw up, you just backspace and you haven't made a scribble mess.
Still, for me that solution has two flaws. One I already mentioned: that continuum of ink pressure is unavailable. They offer "pencil" and "pen" for light and dark but that doesn't convey enough information. More importantly, it means I have to be at my computer.
The optimal solution combines the best of both worlds. Rather than poking away at tiny squares on cheap newsprint, use Across Lite to print full-page puzzles on nice heavy white paper. Then grab something warm to drink and your favorite pen, settle down somewhere comfortable, and get lost in the day's new brainteaser.