1) First, login to your Wordpress.
2) From your Wordpress's dashboard, click on 'Posts' and then, click on 'Categories'
3) Type in the name of the new category you're going to add. For example, I'm going to add a new category named 'Tutorial' as you can see in below picture.
4) The description box, is where you can fill in with the description of the category you're adding. This is optional.
5) Once done, click on 'Add New Category' button.
6) That's it! You've just successfully added a new category that is available for selection when you're creating a new blog post.