Often used in Interaction design, Paper prototypes are lo-fi solutions to test interfaces and their usability.
You can use sticky, transparent papers to create the interface and the different buttons, information... that will appear depending on the users actions. When making the prototype, you should think about the tasks you want to test.
Ask the user to accomplish the task, don't talk more unless he's completely stuck. Observe the reactions and the actions and then debrief. Sometimes you will need one person to "play the machine": move the papers depending on the actions, play the automatic voice and another one who observes.
The Think aloud method can be really useful: it will help you understand what happens in the tester's mind a bit more. Also, don't forget that paper prototypes are so easy to modify, if your tester thinks about a change, just give him a sticky paper so that he can do it immediately when debriefing the task.