A puzzle cache is a particular type of unknown/mystery cache where you must solve a puzzle of some sort before finding the cache. These puzzles can range from finding coordinates in an image to working a math problem to solving a logic puzzle to decoding some encoded information.
Generally, puzzle caches follow two schemes of solving for coordinates. One is that the coordinates can be solved from the cache listing itself, without needing to be on-site to gather data. Sometimes this might require research into a particular field, such as looking up statistics or encoding tables.
The other scheme requires the cache hunter to visit a given location or set of locations in order to gather data required to solve the puzzle. Unlike an offset cache, a puzzle cache will not tell you exactly where and how to obtain the final location. You might be given a general area (e.g., along a designated trail) where you are to gather information, or you might need to figure out how to obtain the final location once you arrive at the location.
Sometimes a hybrid of both schemes are used. Often this involves solving a puzzle beforehand, then going to the solved coordinates to gather data for a later stage.
The containers for some puzzle caches are actually located at the posted coordinates, but you must solve a puzzle of some kind before you can retrieve or open them to sign the log. While a literal interpretation of the Geocaching.com listing requirements/guidelines might indicate that such caches should be listed as traditional caches, listing them as puzzle caches gives seekers a more accurate understanding of the nature of the cache.