To 'Add a new Product Category', from the store dashboard go to:
> Products > Product Categories

From within this page on the left hand side you'll see the heading 'Add New Category'. Underneath this heading you can add a 'Name', 'Slug', 'Parent Category', 'Description', allow the category to be 'Featured', add a 'Featured Image' and input various 'SEO' keywords/terms.
(*Once you've satisfied the relevant areas, don't forget to click 'Add New Category' at the very bottom*)