On the Choose Category screen, select New Category…
Enter a name and choose a colour:
You can also rename and delete/hide categories from this screen by long-pressing (press and hold) on a category’s tile until it expands. It is possible to rename, hide and change the colour of any category, including the built-in categories.
