Paul Boag, writing in Smashing Magazine, talks about the challenges of implementing navigation on really big sites. He considers a range of solutions, drawing on examples including university websites.
I worked with Paul earlier this year specifically on this topic. He did an expert review of my work on the evolution of the University of Edinburgh's information architecture and navigation. He must have been writing this article around the same time (this was done in March, we worked together February).
So much of what is covered here is what he was prompting me to consider and what I subsequently tried out by prototyping deep areas of our site.
Something not covered in this article that is however in the forefront of my mind is, "How easy is it for non-specialist web publishers to get right?" Having an IA and navigation that works well for website users is obviously the primary goal, but if your distributed, semi-autonomous, largely non-specialist web publishing community can't implement it correctly then the user experience through the site starts to fall apart. I understand why Paul wouldn't include this consideration in his article as it's a kind of side point, but nonetheless it's something we're giving a lot of thought to in our CMS UX design and the development of our training and support materials.
Navigation For Mega-Sites - article by Paul Boag for Smashing Magazine