As you plan out your level you should be careful to ensure that the player is never in any doubt as to what they are supposed to be doing.
Its fine to have puzzles as long as the method to solving the puzzle is clear. You can make puzzles as tough as you like though.
A good example of bad signposting can be seen in the early Tomb Raider games. You entered an area only to discover there's no obvious way out. No hints are given as to the possible exit so its left up to the player to explore every nook and cranny trying every action possible. This leads to the player running along walls pressing the action button a million times yelling in frustration and eventually just deciding to drown the big titted bitch to teach the game makers a lesson. (I eventually discovered a hidden zip line at the highest point of that area which led to another area of equally frustrating design).
It should be clear to the player at all times what they are attempting to do and how it should be done. You can allow the player a little discovery every now and again just make sure the solution is pretty obvious when the find it.
So signposting can take many forms. A shaft of volumous light beaming down onto a key on a desk. Using a lit window to guide the player through the darkness. The safehouse symbols in L4D (these are useful but don't over do them. They don't have to be by every doorway).
Another thing the filthy Tomb Raider games were so guilty of was the instant player death syndrome.
The player walks down a dark corridor, suddenly they fall down a hole filled with spikes. YOU ARE DEAD appears on the screen.
The player is given no chance to avoid this death, no notice at all. This death isn't a punishment for doing something stupid. Its a game element that is supposed to make the game more fun when in fact it robs all fun from the experience.
A player death should only occur when they fail to complete a task correctly or just do something plain dumb. Jump off a cliff and instant player death should occur. Fail to run to the end of the tunnel before the train enters it... fine... you saw the damn thing coming its all your fault.
Instant player deaths without warning are evil and should be avoided at all costs.
The best way to ensure that players arnt going to get lost in your map is to get it playtested. What may seem obvious in your warped and twisted imagination may be completely confusing to someone else.
Don't explain anything to the testers. Don't tell them anything other than the general theme of the map and let them go into it blind. If a particular route or puzzle is confusing then more signposting is required.
Also, try to avoid over obvious dialog in the game. Its really rather patronising when you see "OMG look at this wall, how will we ever get past this?" "All walls have weak points! We should look for that!".
Try and be a little more subtle if possible please!