To add a category to your products navigate to the Channels tab and click the 'Categories' step for the desired channel.
1) Categories page
When you are on the categories tab you will see two buttons on the bottom left side. One is 'Add category' and the second 'Generate categories'.
2) Adding categories
Click on the 'Add category' button. This will display an if 'field' contains 'value' rule.
What you can do here is filter on the value of a field, for example: if 'categories' contains 'shoe' then assign category 'Apparel & Accessories > Shoes'. This will assign this category to all products that match this filter.
Don't forget to click 'Save categories', if you don't: all will be lost. When you have saved the changes, on the right hand side of the screen the percentage of items allocated to a category will appear, as well as the number of items set to categories and the number of items not yet set to categories. To see which items have not yet been set to categories click 'without categories' and they will appear in a new screen. Eventually - in the best possible way - you would like to see your categories at a 100%.
The next step is to add rules, see this page for more information.