If u try adding a game to a category, and none exist, it will prompt you to create one (or you may need to click add or create). I just did this personally for the first time a day or 2 ago, and it's very intuitive.
Presumably if categories already exist, on the screen where u can select a category there will be an option to create/add a new category