Creating interesting, original, logical, thoughtful puzzles is an art.
What techniques and methods do you use to create good puzzles?
Do you write storyline before designing puzzles or combine these 2 processes?
Some general inspiring approaches to create puzzles:
One possible inspiring method is to use puzzle classifications.
Adventure UML (Visual representation)
Adventure UML (Source article)
Mark Newheiser's classification
"Making Better Puzzles" by Stephen Granade
All these classifications can be used to stimulate your creativity and brainstorming.
TRIZ - "a problem-solving, analysis and forecasting tool derived from the study of patterns of invention in the global patent literature". It was developed by Soviet engineer and researcher Genrich Altshuller and his colleagues, beginning in 1946. In English the name is typically rendered as "the theory of inventive problem solving", and occasionally goes by the English acronym "TIPS".
TRIZ is variously described as a methodology, tool set, knowledge base, and model-based technology for generating new ideas and solutions for problem solving. It is intended for application in problem formulation, system analysis, failure analysis, and patterns of system evolution. Splits have occurred within TRIZ advocacy, and interpretation of its findings and applications are disputed. TRIZ (wiki)
Edward de Bono's methods of creative thinking. Edward de Bono (wiki)
I prefer to design a situation, model it as accurately as I can, and allow as many standard manipulations as I can, and let problems and solutions emerge intrinsically and appropriately.
Early examples included Infocom's Suspended and FTL's Dungeon Master, though they were a mix of scripted puzzle logic and semi-realistic game systems.
An interesting way to design puzzles is through abstraction - look at objects around your home or elsewhere and think about how they interact with each other, how they can be manipulated and how they could benefit a goal or aim.
Don't forget to think in three dimensions, as this will help with the design of the puzzle space.
Puzzles can be about a whole variety of things applicable to simple day-to-day living. Some examples: shape, colour, memory, logic, primitive maths (addition, subtraction, multiplication and division), sound, depth, light, interaction of lifeforms.
Be sure to tie your puzzles in with the game world and the immersion of the game itself and you will have some thoroughly engaging mind-bogglers.
Experiment. Think about puzzle games you have played that come packaged with a level editor. How would you create a new puzzle using their tool?
Usually by experimenting you can find interesting interactions between puzzle elements.
Working backwards is also a very intuitive way to create puzzles of any sort. I would imagine this is the most common technique. When you know the answer it is easy to build complexity on top of it.
Think of IQ puzzle designers. If I give you a sequence 1,9,25,49,_ and ask you what is next you have to use logic to determine what is going on. Where as from the designers point of view it is just matter of making something up that takes no logic at all: ((n*2)-1)^2
So, I would suggest building a tool to edit levels / elements / etc in your game. Experiment yourself, and allow other designers to experiment. You will see interesting patterns emerge.
Adventure games rely heavily on the same motivations as readers or viewers of books or film. For this reason I'd recommend taking a look at the chapters on the section on the inciting incident and the principle of closing the action-expectation gap in Robert McKee's book Story: http://www.amazon.co.uk/Story-Substance-Structure-Principles-Screenwriting/dp/0413715604
The basic premise is that there is something (the story that you probably want to tell) that sets up a disparity between the expected outcome of an action of the hero, and the actual outcome of that action. This is the gap that needs to be closed by the hero during his adventure. This applies to Adventure game puzzle design by being the technique by which you reveal the new puzzles to be solved: If you know you need A, then you first need to find A, or find someone that can tell you where A is, and when you know that you might need to know how to get there, or how to get A once you get to it. Each thing you need to do to acquire A could be an action, or another item to find/use on another item to create another item/action/opportunity to find another step towards A. Even when you have A/get to A, the final outcome should be that A was not quite what you wanted, but took you someway towards getting what A originally represented as its outcome.
Now, i'll give you an example. You are a cook, and you have broken your frying pan. the story is the cook that has to cook food for your slave driving master. To mend the pan, you just need to get a new handle, the helper recommends using the broken broom in the corner, but it needs cutting, where to find a saw to cut it? Outside, maybe by taking the milk from the fridge to swap for a few moments with a saw... pan fixed, you cook, but the original solution of making breakfast has now been made harder as the time it took to fix the pan has caused the fire to go out...
The expectation of the player should be teased out so they almost always only feel a few clicks away from completing their task, but at the same time allowing the opportunity for a really long list of actions to complete in order to finish the game.
An important part of any long sequence of actions is that the player should know when they are about to finish the game, make sure it's obvious that they are, otherwise the game will feel like they're being short changed at the end, and there's nothing worse than an experience ending badly.
As an adventure game developer (Eternally Us, McCarthy Chronicles) I've found that adventure gamers are generally split into 2 camps. Those who play for puzzles and those who play for interaction and story. Of course there is some overlap but it might be a good idea to establish your audience before thinking about puzzle design.
Those who play for story generally prefer 'puzzles', in a broad sense, with a heavy grounding in reality. This include the more modern post-adventure games like Heavy Rain and Dreamfall. The key with games like this is not to break the immersion and to consider your 'puzzles' as 'challenges' instead.
On the flip side, the old school adventure gamers tend to want hardcore puzzles like they saw in maniac mansion. The best way to design puzzles like this is to start at the solution and work backwards. This allows you to create multi-faceted solutions like those seen in Day of the Tentacle and the other classic Lucas Arts games. These puzzles start with a concept and build the puzzle around it. These games are generally easier to design puzzles for because its acceptable for puzzles to get ridiculous and unintuitive because it is, after all, a 'puzzle. Think of how stupid some of the puzzles with the crystals were in The Dig.
The biggest advice I can give is to play a lot of adventure games. All puzzles generally fall within 1 of several specific categories with well established tropes. Just observe and imitate, then try to branch your puzzles into something new.