Here are some good articles I found while looking for research into the design of puzzle games.
Designing the Puzzle, by Bob Bates, is an article that focuses on the design of puzzles in an adventure game. Regardless of whether an adventure game focuses more on the story or puzzles, bad puzzles will distract the player from the better parts of a game. It includes a list of the fundamental types of puzzles found in games, things to avoid, things to shoot for, and techniques to mitigate the damage that overly difficult puzzles can do.
The overall mantra is to play fair with the player, and avoid such things as player paranoia:
It is very unsettling for a player to worry that the reason he can’t solve a particular puzzle is because there is some tiny area of the screen he has overlooked. If he finds out that this is the case, he will get mad at you.
How are puzzle games designed?, by Herman Tulleken, is a series of articles that begins with some great historical information about puzzles. One of the early examples is the ancient Ostomachion, a tangram-style puzzle originating from mathematical research that Archimedes was doing regarding the division of the square.
Moving Beyond Alchemy is a classic article by Daniel Cook about the use of skill atoms and skill chains for any type of game design.