All products must belong to at least one category, so before you can add any products, you should create the categories required.

If you intend to have a 'shop by category / shop by brand' option, then you should start with just two top level categories (one for each) and nest everything else inside those. Remember that products can have multiple parent categories, so any product can be in both sections (or subcategories within them).

To add a new top level category, go to 'Products > Add New Category'.

Alternatively, you can list the top level categories with the 'categories' icon next to the home button on the left hand menu, then click the 'new' link to the top right of this page. If you want to create subcategories, navigate to the parent category where you want to place the subcategory, and then click the 'new' link. This will pre-fill the 'parent' category into the form.