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 discern at a glance 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 mass of endings.]

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, these devs 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*.
 
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.

Note that blending of puzzle design into a different game structure can be effective as well.
'Outer Wilds' is one of the best puzzlers in recent years, but its merits extend well beyond puzzles, with platforming and 3d exploration and physics-based spaceflight simulation, plus a story that ends in an awe-inspiring and poignant way. Often the ideas seen here are possible to embed into games that aren't strictly 'adventure games' in any narrow old-school sense.

Even Cyan has been known to shift puzzle design to fit changing times, taking the Myst design philosophy and applying it to include physics, multiplayer, realtime 3d, VR... all these modern elements that players today appreciate. So there's no reason not to do this yourself and combine your puzzle design with the more dynamic and immersive traits of modern gaming.   
Ads on TriumphantArtists.com and other websites run by Matthew Hornbostel, include banner ads from Comic Ad Network [top ad - an unfiltered banner rotation system predominantly used by web comics, art sites, but occasionally some questionable items.] and my own banner rotation system [bottom - anything here is either my own stuff like websites, online shops, or social media profiles, or has been vetted by me and found to be generally legit. I have several cashback sites [all of them are ones I've used and cashed out tens of $ from successfully already] and major online retail stores [Sony, Microsoft, Amazon...] in that mix. Usually they give me some sort of small compensation if you buy from them through the link, which I'm disclosing right now. They're all legit spots, but if skeptical do your own research before committing to anything.]