Well, what's the point of playing a single-player puzzle game? If it's the pleasure of perceiving elegant (or at least correct) solutions to a series of puzzles, then looking up answers online is, in a way, cheating yourself of that pleasurable experience.
If on the other hand the point of playing a game is to win -- to conquer and get past challenges -- then looking up the answers to puzzles is not cheating at all; it's simply being efficient in reaching the "win" state.
The point here is that different people are going to approach games in different ways, and it's to be expected that they'll respond to any particular game based on their preferred style of play. Someone who enjoys exploring a complex problem-space will spend hours tinkering with just one puzzle in SpaceChem, while someone who enjoys simple and pleasantly repetitive activities will turn to YouTube a few times before deciding that it's a terrible game, not even really a game at all. (Of course it is a game; it's just not their preferred kind of game.)
So the first thing in designing a puzzle game is to understand that even if you design it for people who enjoy thinking about how to solve puzzles, it's going to be played by people who just want to win. And those latter folks are going to share the answers with the world to prove they won. This is why things like "thottbot" came into existence.
This means the puzzle game designer has a choice: build the game knowing that people will share the answers to every puzzle and hope that the people who enjoy solving puzzles won't be put off by that, or design the game's puzzles in such a way that the solution to each one is unique to that player at that moment.
People have been trying that first approach for a long time now. It doesn't work too well for keeping computer games interesting when it's so easy to share and read solutions.
The second approach is harder. It cuts way back on the number of puzzle types that you can imagine (or borrow from Martin Gardner's "Mathematical Recreations" column in Scientific American). It also has the downside -- a significant one for a commercial game -- that it excludes the "I just want to win" gamer almost entirely. They're not into puzzle games to start with; thinking and imagining and perceiving are not their preferred forms of fun, and when those are the only way to win they won't play.
If you as a game designer are OK with that, then how do you make a puzzle whose solution is unique to each player?
A starting point can be found in SpaceChem. Rather than defining a single perfect solution to each challenge, SpaceChem's "convert these inputs to those outputs" puzzle style allows for multiple ways to accomplish each goal. This means the player can either accept the first solution that meets the requirements, or keep thinking and looking for ways to solve the challenge using either the fewest number of symbols or the shortest number of cycles.
In a way, this design creates two games in one. One game is about finding any solution. This works for the "just want to win" players, who as soon as they beaten the current puzzle can move on to the next one until the whole game is finished. The other game is one of optimization, where the goal is to figure out an optimal solution. The "perception is fun" gamers can still enjoy this kind of puzzle even after the "win" gamer has moved on.
(In a way, this non-binary, "multiple solutions to challenges" design approach is also the theme behind the Looking Glass school of gameplay, as found in games like System Shock and Thief and Deus Ex. I believe this is why these games appeal to the thoughtful/imaginative player as well as the dextrous action gamer.)
SpaceChem's isn't quite the "unique solution for each gamer" kind of puzzle, though. "Win" gamers can still brute-force solutions, and they'll still upload to YouTube the most efficient solutions (in both cycles and symbols) for every challenge.
Something close enough to unique might be a puzzle design where the puzzles are procedurally generated, and where the number of possible puzzles is something like a hundred million or more. A game might consist of a set of 30 puzzles randomly selected from the full set of possible puzzles. Even working together, gamers will not figure out all the solutions and post them online. Of course, in this case you have to be sure that no one can figure out the procedural generation algorithm! (Good luck with that.)
Finally, there's the puzzle design where each puzzle really is unique to each player so that the solutions can't be looked up but must be solved personally. The "elapsed time since the start of play" puzzle in Fez comes close to this form. Taken to its final form, it might be possible to design a game where the kind of puzzle you get in one round depends on some elements of the puzzles presented in previous rounds.
Even for this kind of game, the solutions to the first few puzzles would still be posted online. (Actually, that might not be a bad thing as it would help new players ease into the game.) But the further into the game, the less likely it would be that someone else would have gotten the same puzzle, solved it, and posted the solution. In a way, this is really a variation on the "massive solution space" approach, but it does have the virtue of including the player's actions in the generation algorithm.
There are almost certainly other ways of designing a puzzle game so that each puzzle has more than one correct solution. The overall point is that if you really want puzzles that remain as much fun for the perceptive gamer as for the persistent player, then you need to find a puzzle design that emphasizes perceptiveness and creativity over persistence.
