I've spent regular time preparing for programming puzzle style interviews by working through several books. For whiteboard style interviews I've received puzzles that I've studied before or puzzles that are similar to something I've seen before. I feel that how well I do in this style interview is proportional to how many practice puzzles I've done.

But often the work I'd be doing has very little to do with the preparation I did for the interview. For this type of work I've found that a programing project is a much more honest assessment of my skills. And this is good for both the employer and I.