I don't have much experience with this but I have a few ideas. Obviously it would be very difficult to just figure out all the puzzles in a game in one go. I think it would be best to start with just a story and gradually work puzzles into it, and then tweak it as you go along. I think you should try to keep the total number of items in a game down, and make sure the puzzles aren't too cryptic.