I use a pair process, in order to capture natural conversations.
After giving your subjects a questionnaire for background, set them in front of a machine in a natural office environment and give them a task to perform. My work covers programming tools, so the subjects do pair programming, but the pair approach can work for other programs just as well. The advantage of using pairs is that they will ask each other questions and try to work out the instructions together.
Using pairs is more natural than the common "think out loud" approach, where you tell subjects to say what they are thinking. The problem with that approach is that you won't as easily capture the metaphor that subjects use, which gives you insight into their thinking. E.g., for a compiler tool, "Oh, why is it showing that?", "Hmm, I guess it's like when you are finding a match, but enter the wrong directory?" The trick is that when subjects have to explain their confusion to each other they will have a good reason to make an honest effort.
I use Camtasia with microphones to capture what's on the screen and what they say. I then transcribe the session and annotate with particular actions that happened on-screen. [Camtasia is from TechSmith, the makers of Morae.] You may wish to use a camera to capture the subjects and see where they point their fingers. Going over the transcripts is much more helpful when you are trying to write up what the result might be. [Further: The writing up process itself is helpful to get you to ask the right questions, even if you aren't looking to publish your results.]
After they perform the task, ask them to describe their experience, what they think they would use the program for, what they liked, and what they would like to see improved. Getting this feedback isn't necessarily so that you take their literal suggestions to go implement them. Rather, look deeper to see what their expectations were, and if they were conceptualizing the program differently than you intended; again, to see what metaphors they used.
Also, look at the performance of the task itself. Did they accomplish what they were supposed to? Based on what program you are testing, you may want to time how long specific tasks took them.
Start with a pilot test with what you believe to be a very basic task. You'd be surprised to find that even the simple tasks will take longer than you thought they might. Thus far, I've used what I've gained to change the syntax in my tool, and tweak some features here and there. But the biggest gains I've found is in how I write the tutorial and frame the tool.