I am in the in the process of developing my first App Store-ready iPhone application. One of the most critical things that anyone can do in the development process (on any platform) is to do thorough paper prototypes. However, paper prototyping carries with it a renewed importance on mobile devices due to the small screen sizes.
The iPhone and iPod touch screens are 320 x 480 pixels. Having an life-size sketch of what each interface in your application is going to look like will help you avoid designing an application whose interface is too large for its display.
There are many iPhone stencils and other design tools available. There is the Mobile Sketchbook , originally produced by Dean Kaplan of Kapsoft. The new version of the sketch book includes 1.5x life size blank iPhone screens to draw the interface on. It also includes a plastic stencil with various interface elements, set at the same 1.5x scale.
There is a metal stencil available. It has a 1.2x scale, relative to the actual screen size.
In my opinion, these are good tools for doing quick sketches, but it is important to do a paper prototype that is the exact size of the screen. Since I could not find any life-size iPhone templates, I made my own. It was inspired by the one shown in a promotional video for Cultured Code.
Paper prototyping is a critical part of any development process. Any inconvenience it might provide you in the short term will ultimately save you time and help you to create a well-planned and easily used application.