you will nee to use CSS Menu writer for this to create the dynamic menu.
before you start, you should go through the "Creating Dynamic Menus with CSS Menu Writer 2.0" tutorial on the menu writer support page to get familiar with generating a dynamic menu:
css-menu-writer/
also get familiar with the search and results page.
the search page should pass the category as a URL Parameter, there should be a couple others as well, your dynamic menu will ned to pass those same URL parameters.