There is a lot to be said in favour of testing with paper prototypes, the main advantage being that you can test concepts very early without a large overhead of design and/or development. I found these videos linked to on an article on the Interaction Designer’s Coffee Break.

“Drive-thru” interface testing

Paper prototyping a web interface

Paper prototyping a mobile interface

I wrote recently about my liking for “sketchy” wireframe stencils and I think that testing these wireframes, like these paper prototypes, has a lot of merit.