I think the way the docs are laid out is pretty logical, but not necessarily intuitive. I see a lot of people give up digging through the index manually and favor the Google route, instead of exterting the extra effort to find exactly what they need from the index.
I forced myself to learn to use the documentation properly after being bitten too many times working off of documentation located via Google which applied to an incorrect IOS version or a dissimilar hardware platform. I put together a short guide to illustrate the strategy I use for navigating the docs to hopefully help others: http://packetlife.net/blog/2010/mar/8/navigating-cisco-documentation/
I have no doubt the documentation maintainers could come up with something ten times more elegant than what I did. Just a short tutorial, maybe five minutes in length, accessible from the main documentation page. "First time using the docs? Read this to get started!" That sort of thing.