Kinda depends on how nonlinear you want to go.

One model is the "string of pearls" idea where there are bubbles of nonlinearity connected by bottlenecks that the player must pass through to proceed to the next bubble. Each bubble can be 2-3 rooms, or 10 rooms, or an open terrain area. The bottlenecks can be things like a locked door, where the key is hidden somewhere in the bubble.

A version of this where the bubbles overlap is RickyT23's map, Stark Monstrosity, which is basically a stack of loops. Each loop has a specific way to get up to the next one, but unlike the string of pearls, they actually overlap and you can fall down to an earlier part of the level. The nice thing about the loop approach is there are no dead ends. I think this layout is called a "braid maze."

There was a Doom 2 city level that had a design where it was practically one giant open layout, and if you wandered around you'd eventually find a blue door, a red door, and a yellow door. Then you will eventually find the yellow key, and behind the yellow door is small-ish interior with the red key, and behind the red door is a smallish interior with the blue key, and behind the blue door is the exit. This is basically identical to the way quake's E1M5 works, except in E1M5 the "hub" is about 10% of the level's real estate, and most of the level is the 3 "spokes", whereas in the doom 2 level it's about 90% of the real estate, and the 3 spokes are small.

Anyway, that's all kind of vague, but if you do any of that stuff, the key is that you need really good landmarks, or people will wander around and not be able to figure out where they are trying to go or where they have already been. For example in ricky's map, i think i looped around twice looking for the silver door. Make sure it's not easy to walk by the important door without noticing it. 

doom and heretic had good examples of large, nonlinear-style maps. for example, Mount Erebus from doom episode 3 Inferno - you could wander around and you had to visit most areas of the map (but not all) to collect enough keys to get to the end, but it was really nonlinear. heretic's e1m5 The Citadel was also basically two open areas linked by multiple bottlenecks (one key would let you get from area 1 to area 2 using any of the bottlenecks).

I like nonlinear. It's a tradeoff for the ascent-type thing which I also like (Breakfast at Twilight, or Masque,etc). Possibly the two could be combined using an item like a grappling hook, anti-gravity belt, or jump power increaser, or even flight. 

Descent had the same blue yellow red door mechanic, and it worked great.

It's also important to have a clear goal defined. Staged door codes (bronze, silver, gold) can help lead the player - in descent it always was (blue, yellow, red), in that order.

In hl there's the tentacle thing in the rocket shaft, and you need to switch on oxygen and gasoline (and one other thing?). I think their implementation has a slight problem with the obviousness of the goal, though. That most games' environments are so limited (you just stop adding detail / thought / logic after you reach a certain level of detail) leads to players that are simply not used to think about their environment that much, so you kinda have to push them towards the details that are important to understand the non-linearity in your level. An announcer ("Can't start deadly rocket test because there's no gas or oxygen!") would probably make everything very clear, but of course it can't be too obvious, so the player still gets a feeling of accomplishment.

I think environment design plays a big part in this, too. Not only do you need landmarks, you also can use environments that lead to a certain goal. In diablo, you always know that you have to go deeper to get to the end of the game, although there's no other hints in the levels. The dungeon mechanic simply suggests this.

If you do not have an environment that does this (e.g. GTA-like) you need to provide strong directions by other means. You can have characters talking to the player, hinting him towards the right location - think detective story, where the protagonists follows a hint, gets a new one, follows that one... just like a string of pearls. Note the duality of environment design (metl) and hints (detective story).

Of course this can also be inverted. It makes sense that the holy grail inside the secret base is actually secret. Just don't make it random, keep in mind that you need to provide directions to the player. I'd advise against making these too obvious and singular, though. A surrounding environment is much better than a single sign with an arrow on it.

Because quake is so simple, landmarks work much better here, simply because it's easy to remember 5-10 landmarks and recognize them when you return. Still, it's nice to know that I just need to climb to the top of the tower to find the exit, but well, I'll just explore on this level some more. Of course you can go much more complex than this. If your goal is to switch of the water supply to a city, you need to find the way to the water facility, then the control room, then the keycard to use the terminal, etc. 

This is something I should read, my maps are always very linear I have always had lots of difficulties to make nonlinear maps :\ I guess doesn't help much the fact that I usually design with gameplay in mind.. in all my maps, I add gameplay at same time I make a room...
I should quit that... but I always forget when I start something!
Need to start mapping again, now my life is much more relaxing, my oldest is 7 and smaller 3 and they already give me free time for me, will try to reserve at least 2 hours a week! 

http://forums.inside3d.com/viewtopic.php?t=2307 

There's a Duke3D user map called Roch 7, which adds a form of non-linear gameplay. Basically we have this city/street area with many buildings you can enter, each one locked with a blue key card. Only one of them is locked with a yellow key. Having only a single blue key in hand, the objective is to pick a building, navigate through it to find a specific type of switch and another blue key. Once all these switches have been pushed, it will reveal access to the yellow key which ends the level. Also to note, pushing one of those switches may trigger a few enemies to spawn within the street area. 

Should have done this above, for those interested;
http://dukerepository.com/maps/Roch_7 

Circular layout I remember is from czg07b I think. It has the player revisiting the same area around four or five times. Granted its a very big vertical area, but once you figure it out its pretty cool.

Circular route maps are best I think, although lineal levels can be great as well - the mexx9 series are a great example of well realised lineal level making.

Genuinely open maps in Quake aren't common, because they're hard to do without the player becoming lost or feeling like they don't have a purpose.

Buildings are a good way of dividing the map into sectors that are easily recognisable - Nehahra did this well in forge city.

The Palace of Hate is a great example of open mapping, with a couple of loops thrown in.

Doom was a better example of open mapping since there were less mechanics to confuse the player with it was always (key -> door).

Typically 'follow the enemy road' works best for directing the player, especially with enemies that don't move much. Basically, put enemies where the player needs to go.

Another method that's worth mentioning but hasn't arrived in Quake is breadcrumb trail. Leaving a string of weak powerups that show a route - if the player has been in that direction then they'll have collected the powerups. This is helpful in multiple route areas, like a Pacman maze.

Will probably ramble some more on this later. 

In Polygon Base for Doom2 the 3 doors were at the very end, you had to wander the map to find the keys.

http://www.doomworld.com/idgames/index.php?id=4529

Well of Wishes for Quake (which I've been working on a re-make of) was semi-nonlinear. 

Then activate the back-up generator to restore power.

Just don't forget to make areas distinguishable from each other. 

is one of my favourite Quake maps. So good. 

i've been toying with the idea of making a city map where there's tons of buildings... and you don't have to go into any of them. in theory, you'd be able to just waltz over to the end area and hit the changelevel trigger. the idea being, you can play as much of the map as you want.
probably a dumb idea though. maybe if the map constantly spawned monsters for you to fight or something... 

That could be interesting if the exit was not always in the same place, or if the exit moved every so often...

Hmm... you can killtarget changelevels... 

Or there could be an exit door which requires a silver key to open, but the silver key spawns in a random building. Somehow. 

Somehow.

http://celephais.net/board/view_thread.php?id=60427 

One idea is if the map focused was entirely on finding secrets? And a rather high count too, I'm kind of thinking on the lines of those Secret City maps for Sven Coop. Finding them all is the 'true' ending, or you could just waltz over to the easy exit, putting emphasis on exploration and dealing with the threats you come across (enemies/environment). 

yes, i think something quite like that really.
you could use the hl2/portal style storytelling to entice players into bothering to look a little deeper instead of making a bee-line for the exit, but secrets and stuff would be there as a catch all for players who just don't care about story. :P