Jürgen Schweizer: We do a lot of work before we even start thinking about an interface. We start out by having lots of conversations, really talking through what we want the app to be. The most important thing is to understand what you're trying to achieve at the conceptual level: what problem do you want to solve, what kind of users do you expect to have, and what are their expectations? Many designers jump ahead and start working with interface controls before they even figure out the user's mental model—what problem they need the app to address.
Once we know what we want an app to do, we move to paper to start working on interface sketches and mockups. We build flow diagrams of every screen, with arrows drawn between them so that we can see exactly how people will move through the app (see Put Something Ugly on Your iPhone). You can really do a lot on paper, but you never know for sure whether it will work until you build it and try it with actual users. Still, we start building only after we've planned the whole thing because you can't give people a half-finished app to test. You have to have a full implementation for them to try out, and that means coding an entire app before you can give it to testers. That's why it's so important to do these paper sketches first, to have a solid plan in place because you really don't want to recode the whole thing over and over again.