An interesting interview with Hagan Rivers on uie.com about how she approaches navigation. She's talking about web applications like online shopping carts here, but the principles apply equally to 'ordinary' website content.
She suggests treating the navigation as a separate development. So, for the majority of her time she focuses on the content of the screens - working with users and stakeholders to get these right - with the navigation effectively blanked out. She works on scenarios where she doesn't worry about how the user got to a particular point. She just focuses on the interaction there and then. Only when she's 60 to 70% of her way through the project does navigation begin to be developed.
I like this approach because it tallies with what others say about web development and how we try to progress our projects: the strategy drives the content which in turn drives the structure.
So often a structure is put in place before there is a clear set of objectives for a site (if they ever materialise at all!), and before much (if any) content is written.
Escaping navigation hell - Jared Spool interviews Hagan Rivers (listen online or download mp3 podcast)
The page also contains a good overview of the podcast, with the most pertinent quotes included.