Summary: With a paper prototype, you can user test early design ideas at an extremely low cost. Doing so lets you fix usability problems before you waste money implementing something that doesn't work.
In my experience, designers almost never use paper prototyping in real design projects despite its potentially immense contribution to creating a high-quality user experience.
Too Simple to Be True?
Why don't design teams use paper prototyping? Is it because it's so expensive and time consuming that project managers regrettably decide to allocate resources elsewhere so they can ship on time? No. Paper prototyping is one of the fastest and cheapest techniques you can employ in a design process.
Paper prototyping isn't used because people don't think they will get enough information from a method that is so simple and so cheap. It feels like you're cheating if you attempt to improve your project without investing more of the sweat of your brow. "It's too easy; it can't work" goes the reasoning, and "we should wait until we have a better user interface before we show it to customers." Wrong. If you wait, it will be too late to translate your usability findings into needed changes in your design's direction.
I'm here to tell you that paper prototyping works. There are many different grades of paper prototypes, and they all offer immense value relative to the time it takes to create and test them. I have run studies with nothing more than three different homepage mock-ups for a website, and still we learned a lot about how people would use the service and how our design concepts communicated to users.
Why Paper Prototypes Save Money
Twenty years of usability engineering experience uniformly indicates that the biggest improvements in user experience come from gathering usability data as early as possible in a design project. Measured usability can increase by an order of magnitude when you can change the project's basic approach to the problem, change the feature set, and change the user interface architecture. Usability insights also help later in the project, and there is value in fine-tuning user interface details, but late-stage changes impact the final user experience less than fundamental changes early in the design. It's a rough estimate, but I would say that the benefits from early usability data are at least ten times greater than those from late usability data. Late usability studies often add about 100% to the final design's desired metrics, but early usability can add 1,000% or more.
Forty years of software engineering experience uniformly indicates that it's much cheaper to change a product early in the development process than it is to make changes later in the process. The most common estimate is that it's 100 times cheaper to make a change before any code has been written than it is to wait until after the implementation is complete.
So: Ten times the impact if you discover a needed design change early, and 100 times cheaper to make the change. The experience from both fields is clear: early is much better than late.
The benefits from early user research are so vastly superior that you should definitely use paper prototyping, even if you don't think the prototype will be as good as testing a fully developed design. If you simply try it, you'll be surprised at the amount of insight a "primitive" prototype can offer. Even if you don't believe me, believe the collective experience of usability and software engineers: Early beats late by so much that it outweighs the differences in prototype quality. (It may be "Lean UX" but it's also "mean UX" in terms of the ability to bite off large parts of bad design and replace with good design.)
A Usability Method That's Here to Stay
Paper prototyping has a second benefit, besides its impact on your current design project's quality. It will also benefit your career. Consider all the other books you've read about computers, Web design, and similar topics. How much of what you learned will still be useful in ten years? In twenty years? In the immortal words of my old boss, Scott McNealy, technology has the shelf life of a banana.
In contrast, the paper prototyping technique has a shelf life closer to that of, say, paper. Once you've learned paper prototyping, you can use it in every project you do for the rest of your career. (See photo of a paper prototype test from 1995: it looks exactly the same today.) I have no idea what user interface technologies will be popular in twenty years, but I do know that I'll have to subject those designs to usability evaluation, and that paper prototyping will be a valuable technique for running early studies.
Paper Prototyping: A How-To Video, 40 minute film available for download that demonstrates practical techniques for building the prototypes and testing them with users.
I made this training video because most companies don't believe in a technique that is this simple without actually seeing how it works. Video does this job well.
Carolyn Snyder: Paper Prototyping: The Fast and Easy Way to Design and Refine User Interfaces. Even though it is from 2003, the methods don't change much, so I still recommend this book. See Amazon.com's book page or Amazon.co.uk's book page for more info.