Many times the solutions to the puzzles are coordinates so you want your victims to harness their problem-solving skills. With that in mind although, be advised that it's not always the case. Employing riddles is always a possibility whereby the answer leads to the geocache stash or another location where another riddle needs to be solved before the final boon is revealed.
You already know the basics of geocaching when you decide to get into puzzle oriented Geocaching. The best way for you to learn how to make your own is to become familiar with the types of puzzles already in use at geocaching sites all over the world. By seeing how geocachers have created and solved puzzles ranging from easy to very difficult, you will be well on your way to making your own particular brand of brain teaser.
The following is a good list of the types of puzzles you can create in order for people to locate geocaches: trivia/current events; wordplays; math; logical reasoning problems; cryptograms; hidden or deviously encrypted messages; sudokus; and lateral thinking which is essentially thinking outside the box.
The best place for you to learn all the ins and outs of puzzle-solving and puzzle-making is the The Official Global GPS Cache Hunt Site. Some of the best information is already assembled there to better assist you with this task. There you will be presented with comprehensive information on all the riddle making techniques so you can challenge those on a GPS assisted quest to find their scaled down versions of the Holy Grail.