Steven's answer is great and it allows you to do clever things with faceted search and filtering later on. Don't forget that Categories can also make use of custom fields which is helpful if you want to build a Category 'home page'.
Another route is to leverage Crafts Relationships capability.
If both Products and Brands were Channels, then you can add an Entries customer field within you Products Entry Type - so that when you publish a product, you get to define which Brand it is related to.
This would allow you to relate other Sections / content-types to a Brand as well.
Ultimately, there are a million ways to skin this cat, I suggest taking into account the requirements for the entire project and how they may evolve and deciding on a project by project basis.