Adding a category to a video is one of the steps needed for it to appear in your catalog (the other is it being published).

Navigate to Content > Videos > More options (...) and select Edit on the video you want to add a category to.

Scroll down to Organize, and you'll see the Categories section at the top.

Select the category you want to attribute to the video or create a new one by clicking on +Add New Category.

A video can appear in as many categories as you would like.