Also, one thing you absolutely must do is make sure they can program!
Have them solve some simple programming problems and maybe design problems. You can use plenty of flexibility here, even give them some time alone to do it if they have difficultly doing it in an interview context in front of people on a white board, but be sure to do it.
In the bad old days of C/C++ a general approach was:
Write code to reverse a linked list. Very common, tests knowledge of pointer use.)
As a warm up, perhaps write code to compute the factorial of a number. You can test knowledge of recursion this way and the mathematical function is so simple that shouldn't through the interview for a loop (e.g. computing Fibonacci numbers is too complex for an interview in my opinion).
And show them a block of code/a small function that's got some deliberate errors etc. in it and ask them to find all the ones they can.
You aren't looking for perfection in this sort of stressful situation, but you do need to know if they can program their way out of a paper bag. Many if not most self-described "programmers" can't.
As for design, there are many ways to approach this, and I like doing some of it interactively, i.e. talk with the candidate as they are doing it or after they've had a little while to think about it, scribble on paper, etc. You want evidence of their design thinking, not a perfect or complete design.
[1] http://www.amazon.com/s/ref=nb_sb_noss?url=search-alias%3Dap...