There is a lot being done to solve common navigation / usability problems. I had a look around the web, here are a few of the more interesting ideas I've found.
http://www.decursor.com/Zoeken/ - In the advanced search on this site (in Dutch), there is a dropdown with most often used search terms. Any programmer will ask you why that's necessary, but I believe it's a brilliant idea, the genius of it lays in its simplicity. It takes the pain out of searching.
It shows you what people are searching for, and gives you the feeling you will get good results from this. It makes the search easier. Most importantly: you don't have to figure out which search terms to use. I am thinking about putting it right next to the search field on my site on every page.
I think it is the most useful addition to the plain text box you can make in a search function (apart from search certain sections of the site, which on some sites is pretty useful).
http://invisibleweb.com - Easy to use personalization. It's yahoo-like but easier. I especially like the up/down arrows, which are really (and let me use an often abused word here) intuitive. My.yahoo.com is the granddaddy of personalisation, and it's pretty good, but this site is fantastic in its simplicity.
Some sites let you keep your own 'bookmarks'. One site (lost the url) has a button 'add this page to my list' and there is a list of pages in the top right corner. This seems to work well for sites you would be doing research on. It is more or less the print basket functionality I talked about earlier.
http://www.ft.com - A big problem with navigation on complex sites is: how much do you show. Show too little, and it will be harder for users to navigate (I am talking about compelx sites here). Show too much, and you?re taking up too much screenspace.
FT solved this by not showing any navigation, only a 'view navigation' button and a search button. It doesn't reload te page when you click the view navigation button, just shows the navigation, so it's pretty useful. A great idea.