There are two places. If you want to create a bunch of categories at once, go to posts > post categories in your dashboard and you can create them there.
If you want to create them on the fly as you write posts, then you can do that in the post editor page as you write your post in the categories module that is typically to the right of the text area. There is a "create new" link in that module.
For existing posts, if you wish to go back and categorize them, just open them in the editor and assign the category you want and uncheck the "uncategorized" category and then update the post.