How do you sketch out your iPhone App designs and ideas?

For the first stage, nothing is going to beat paper. Whatever tool you use will be (hopefully) more accurate, sure. But you're trading time for that accuracy, and in the initial stage of UI design you need speed more than accuracy.

I do my designs with a few different pencils on index cards. When I'm satisfied I'm going in the right direction, I tape the card to a ruler and use my iMac's camera to take a picture of them. I then convert it to B&W and do a simple brightness/contrast to try to get them looking as good as possible, and I've got something reasonable to digitally store.

The great thing about this is that I can draw a rough card in not much more time than it takes Save As to open up if your Time Machine drive has gone to sleep. :) I can do a nice card in a little more time. And if I ever want something nicer looking, I can edit the scan or use it as a tracer in some other program.

(And I toss the cards in ziplock bags by project.)

Balsamiq has an excellent tool for doing mockups of interface designs. They also have some iPhone components. There is an online demo that I have started using (after seeing the answer to another SO question) and have really enjoyed the experience so far.