The creation of a good puzzle depends a lot on the specifics of the puzzle and your intended audience and medium of presentation. Let's take Puzzling.SE as an example, as you've used that in your question. The folks over at Puzzling.SE wondered something similar as you do and decided to post their creation process in "Wrap-Up" posts. You can find concrete examples of such Wrap-Ups for example here. By searching for these duplicates on the site you can find lots of incredibly detailed information about specific kinds of puzzles. The linked example provides insight into the creation of a puzzle involving four-line riddles, which could easily be incorporated into a novel or similar written medium.
To summarise some important points from the linked example:
- the OP used existing puzzles as inspiration
- they found stuff in them that they first interpreted differently
- the different interpretation was used together with the original content as the starting point for their own new riddle - they already had the hints and a new solution
This approach has many advantages. For example you can take the original as a starting point to judge whether you think the puzzle was good in length, style and difficulty for the intended target audience. Most of the time you will be able to judge these things for yourself or by looking at the avenue that the original was posted and looking through the feedback the original got, such as the answers and comments on a different StackExchange site.
But just by looking at the linked example you can see that it's often incredibly difficult to judge whether something will be too easy or too difficult:
Honestly, I'm still not sure whether I got the balance of difficulty right: I was expecting it to last a few days, but it was solved within ten minutes. Whether I made it too easy or Sconibulus is just too clever, I have yet to work out.
If you have a puzzle you want to use in your own writing the best thing would be to find a friend or a group of other writers that could be considered close to your target audience. Let them try to find the solution and you will have an idea of how easy / difficult the puzzle is before releasing it. The closer to your target audience the better. Though a little diversity can't hurt to see how others react to the puzzle.