How add categories / subcategories to CPTs?

Hi – I am just setting up my directory and can’t figure out how and where to set up categories. I have searched the documentation for two hours but it eludes me!

I have set up a bunch of CPTs, such as Restaurants, Shopping, Travel. Now I want to add categories within the CPTs. So for example:
Restaurants:
— Vegetarian
— Vegan

Shopping:
— Clothing
— Home Goods

Would you please tell me exactly where I need to go to do this? The instructions say I need to add categories, but I don’t see where, and I don’t know if it’s a different place if there are CPTs, and how to connect the category with the CPT.

Thank you very, very much!!