In your head at 1st. Get an idea/theme for your game, then think it through seeing if it is logical and where the idea will go. No use having a theme that has no logical progression.
Next write it down, as your story is the backbone of your game. Read it back and make sure it feels compelling and once again logical. Most players are intelligent and will always compare fiction to real life to a certain extent, picking holes in any plot or special effect etc.
If you right down your world, it's structure, culture etc, you won't find yourself lost for ideas whilst building on the idea and thus building your maps.
Draw your maps on paper. FPSC is grid based, so perfect for making use of graph paper to make sure your map ideas will work out the way you want them to. Bugsy is very good for planing on paper 1st, then putting it into FPSC.
At every point of game design, sit back and look at what you have done and think "what would the player do?", "what would I do in real life if presented with this scenario?" Yes games are not real life
but it can drive the brain mad when things are just so illogical, unless the entire game is made to exploit that aspect of course, like a dream state etc.
Never! just get an idea and start slapping down rooms, filling it with enemies as you go. That is what we all did (well I did) when we 1st got a games making kit using it like a map maker for an existing game. This was fine in the days of making maps for Doom and Quake1 etc so we could send to our mates, but this will never make a compelling game.
Most people are curious and inquisitive. Feed on that making the player always think "hmm.. where is this going, what's through there", but in a good way hooking them to the plot/story. We have all played games that pulled us right in only to find the birds are singing outside our window with the sun rising ^_^
With map design always think while placing stuff "why is this here??" i.e. like a light in a room needs a source for that light, a sound effect needs a reason for it, debris should always reflect the surroundings (no use having brown bricks from a grey wall hole etc). Take the saw blade corpse everyone loves to pin to the walls and the bodies on hooks. Yes they are excellent models and I feel you for wanting to make use of them, just think "where did that saw blade come from??" or "why are the hooks here?" because I can tell you the player will.
Always build the suspense, atmosphere and game in general as the game progresses. Don't just give the player a gun and swamp him with rooms of enemies, topping up his ammo/arsenal between rooms.
Build it up, start simple with a little exploration, story telling. Nothing wrong with having an entire level with little to no threat, just a getting to feel it all level where you can get the player hooked, build up the story etc. A few sounds effects, low atmospheric music/sounds, maybe even a few "damn what was that! that shot past that door/hallway" type things so the player starts to get worried
Well that's my thinking on the matter anyway