Need help with WordPress eCommerce menu??

Hi,

Im stuck with a problem and i was wondering if their is anybody who can help me solve it.

I have a client who has a wordpress ecommerce website and he wants his products to interlink together in the menu's becuase his other developer forgot to put it in the theme so now he wants me to try and figure it out.

He has a fashion website and when you click on to a brand / make he wants it to come up with products what are related to that brand / make........ so if your in the handbag section he wants to be able to narrow down the search by clicking the menu on the right hand side to a certain brand for example handbags>D&G what comes up with D&G handbags.
He also wants it so when your in the D&G section you can click on items what are related to that make so glasses belts etc etc.

How would i go about making such a menu in wordpress,
Would everything need to be a catorgrey and then style each menu to each page? Seems a hell of a lot of work, how would you approach this?

Any help / advice would be extremely helpful!

Cheers
Cloudy

Taxonomies is your friend:
http://net.tutsplus.com/tutorials/wordpress/introducing-wordpress-3-custom-taxonomies/

Thanks man, that seems to be what im looking for now its just about integrating it!