Pro tip: buy a sketchbook that has both a 24 column grid and browser chrome, so it'll feel more like the final product and give you a better sense of proportion. But don't be afraid to chuck it for something even more low fidelity, like butcher paper and sharpies.
Here's the one I've been using - it has tear-away pages and alternates between full-width and 2-on-a-page layouts:
http://appsketchbook.com/products/ux-sketchbook
Best $12 I ever spent. I also a fan of the double-ended art markers by Prismacolor - they're basically like highlighters but in a variety of colors, like a subtle gray. I like adding shading with those instead of dealing with the messiness of pencils and erasers. That's how I make sketches like these: