I've been thinking about these kinds of features too, they're something that we'd like to be able to get in to 2.2. I've got a bunch of interesting search links that I've been posting to del.icio.us:
if you're interested in following along. One of the nicest looking example I saw was this screenshot:
which I think is kind of the same thing you're talking about (that particular implementation is using a technology made by Boston-based Endeca). I've heard this feature referred to as faceted search.
Let me know if you find other screenshots that represent the ideas you've talking about.
Hi Aaron - I just stumbled across this post and am very interested in implementing a faceted navgational structure as detailed in the following by my new favorite person Professor Marti Hearst: http://www.slideshare.net/marti_hearst/faceted-metadata-for-site-navigation-and-search. Is this something we can expect in v4.5 or is it already around?