What makes a good puzzle game?

Well, there are a lot of things on top of the core game design, like graphics and sound, but right now we'll focus on actual puzzle design.

There are some games that have piles of self-contained puzzles, which you can see in the likes of the 'Myst' series and the typical escape room, or for that matter 'The Room' series on iPad, or various old-school classics like 'Grim Fandango', in which a series of puzzles must be figured out individually and they unlock more of the story and gameworld.

The modern tendency goes against this and opts for a few core mechanics or ideas, and consistent rules underlying every puzzle in the game. This is wise insofar as it gives a player something to go on when going from one challenge to the next.

For example, "Portal" and "The Talos Principle" give players numerous components and an end goal, and task them with figuring out how to reach the end goal. Some components may be new or may be used in surprising ways, but the player has learned from preceding puzzles, at least much of what they need to know to complete the next one.

It's good to give players a sense of 'what am I trying to do' and THEN giving them some stuff that they must then figure out how to use to get there. It's also good to start simply and add increasing difficulty as puzzles progress, adding new rules and elements to the design steadily as the game continues and forcing the player to figure out what those elements mean, what they do, and what the implications of them are, in context of a larger set of puzzle elements.

Puzzle designers may find it useful to work backwards, starting with a 'solved' state and then shuffling things backwards to an unsolved and confusingly jumbled state such that the way too get the solved state from the starting point is not obvious.

One common metaphor, and the most cliche puzzle in existence, is the notion of a lock and a key.
The lock is the end goal, the key is used to open it. Now imagine obfuscating both lock and key into something else. Maybe it's another inventory item that does something, and maybe only then when put in a certain state, and continue from there. But far from being a sadist, the puzzle designer actually should set out to lose. The objective of designing a puzzle is to make it solveable!

Often this means a key leap of logic or insight on the part of the player will be required, an 'aha!' moment where things suddenly make sense and all the available elements fall into place. That must be a goal, and Jonathan Blow ("Braid", "The Witness") has outright said that a puzzle designer's aim is to manufacture epiphanies, those moments where everything fits together and falls into place.

So obviously there are pitfalls inherent in this. Puzzle solutions may be too obvious, or too difficult, which makes this a hard sort of game to design in many ways. Solutions ought to be specific, such that they're only going to be solved intentionally, not by accident or brute-force entering of random input. They should also make logical sense after the fact, not resorting to 'moon logic' that is absurd. (An infamous example of moon logic is the 'cat hair moustache' puzzle in Gabriel Knight 4, in which the solution is utterly arbitrary and nonsensical.)

Puzzles should not take forever to execute once the solution is figured out, they should ideally be tougher to understand than to execute once understood. Red herrings are also problematic, it's helpful to know what is and is not, likely to be a puzzle element. "Obduction" (by the Myst devs at Cyan) is a beautiful game with wonderful art direction and mood/story, but there are moments where it fails in both of these. Execution of some puzzles requires a lot of loading and unloading of levels and moving back and forth which means slow execution of otherwise easy conceptual design, and there's a stupid box with symbols and buttons, that looks like it must be important but no, it is not at all required in solving the game and amounts to a confusing distraction. [Though, to be fair, certain codes input into it do hold easter egg images. So it's not 100% useless.]
Art design and lighting can be extremely helpful in calling attention to things that actually have utility in a puzzle. Cyan's games struggle with this and tend to confuse players, largely because they have such beautiful and intricate-looking gameworlds, which has the unfortunate side effect of making it hard to see what matters in them and what is inconsequential.

But to their credit as well, they do have a sense of place, with environments being more than simple, minimalist 'puzzle chambers' as seen in the likes of 'The Turing Test', or 'Antichamber' - they feel like lived-in worlds with histories and stories behind them. I'm actually a massive fan of this balancing act they pull off and I also, in many ways, prefer a story and a setting that is concrete and structured to one that is so thoroughly vague and ambiguous that it's more philosophical expression expressed through the intrinsic themes and mechanisms of the puzzles/gameplay, than a real story with a conventional and satisying ending. [i.e. : The Witness, which has a ton of puzzles and lots of good ones and a beautiful 3d world but a divisively anticlimactic, open-to-interpretation ending.]

All that is to say, that story, setting/level design, and puzzle design are all important to mesh together well, and if they don't it can be deeply problematic in a wide range of different ways.
And I don't want you to think I am a hater of Cyan or of Jon Blow, they do an awful lot right. But this is just a very... inherently hard genre to get everything right with. Heck, I even have a Cyan/Myst/adventure-gaming fansite*. [see links below] 

Finally, puzzles cannot be pushed into a state in which solution of said puzzle is impossible; if this is the case, designers should at the very least allow for a reset or save/load option to shift things back to the initial setup. There is really no excuse for not including autosaves and manual saves, and really there should be a reasonable number of save game slots available.

  
The banner links at the bottom of each page include links to my own webpages, links to my storefronts/shops online, and occasional links to other [third-party] verifiably legitimate stores and services I've hand-picked, vetted, and used myself. 
That said, I'll openly disclose that when you buy something from another vendor using these links, for example, a link to Amazon.com, I will get a small fraction of the sale amount and will use that as a means of supporting and expanding the projects I'm working on here. These ads for other vendors, as well as - especially! - links to my own shops, are helping me keep these sites online and growing with new content on a more frequent basis.