A paper prototype is a way of demonstrating the way an user interface works without actually programming or building the UI on computer. It is cheap, it's fast, it's very effective, and above all, it's fun for all who are inclined to do so. So, it's a very widely used method for prototyping user interfaces and demonstrating the UIs for people who ordered its design.
As the name implies, the UI is drawn on paper, and all possible changing parts of the UI are made into small bits of paper. The "computer" is represented by a human who moves the bits of paper around. The user then "clicks on buttons" and "types" and does things he would normally do with the system; Pushing a GUI button might bring up a dialog box, which the "computer" then places on the "screen".
There are variants of this method, for example, using some interactive graphics program (such as Macromedia Flash) to simulate the UI - but even when these are relatively easy to do, this still is not as fast as making the UI out of paper...