Correct way to create Departments/Categories cck selectors in Drupal 7?
Your concern is true. Anyone that tried to build an eshop with multiple categories had the same question in the beggining.


  1) how I should structure my data in taxonomies or other structures (menus?)


You can create a large taxonomy tree the way I see it on the screenshot. Use taxonomy_manager for better UI. Also to display the taxonomy trees as mega menus you can search for "mega menu" in the drupalmodules.com you will find many such modules.


  2) how to create the cck fields for the manufacturer to add multiple department / categories to his product


You can use the Hierarchical_select module. It is a must for such functionality.


  3) how he can add a brand to his product or create and add a new brand to his product


Create a new Vocabulary for Brands and add a field with autocomplete. You can use Hierarchical Select also. It has an option (with proper permissions) to add a term if it does not exist.