Creating Robust Taxonomies

I wanted to follow up on Shara's posting about creating taxonomies. 

I just joined a new company and one of my first projects is to improve the search experience, most likely by implementing a faceted search.

The site (& search results) is very domain-specific and I'm new to the topic so I imagine I'll be consulting with a lot of people throughout the company.

Any suggestions/help/past experiences in doing something similar would be fabulous to hear about :)

thanks!