Before I hit the paper I brainstorm with someone who might use the project.

Then I spend some time sketching out the main user "actions" on paper, do a quick database table layout on paper (connecting pieces of information), then I sketch UI concepts in my notebook.

Of course, as a designer at heart, I open photoshop and blast as soon as I have some pen/paper wireframes ready.