// First we create empty category model
$newCategory = new CategoryModel();

// Now we assign our new category to category group.
// You can find category group id inĀ /admin/settings/categories.
$newCategory->groupId = $categoryGroupId;

// Give our new category a title.
$newCategory->getContent()->title = 'Category Title';

// Save category and check that everything went ok.
if (craft()->categories->saveCategory($newCategory)) {
    // All fine
    ...
} else {
    throw new HttpException(500, Craft::t('Unable to create a new category.'));
}