I have found one solution.
I needed to use the Category Search plugin by Vladimir Prelovac.
Then, I had to tweak it a little, namely, change this:
if (strpos(strtolower($cat->name),strtolower($search_string))!== false)
{
$name=attribute_escape( $cat->name);
$link=get_category_link( $cat->term_id );
$desc=$category->description;
$output.=$before_list.'<a href="'.$link.'">'.$name.'</a>'.$desc.$after_list;
$count++;
}
to this:
if (strpos(strtolower($cat->name),strtolower($search_string))!== false || strpos(strtolower($cat->description),strtolower($search_string))!== false)
{
$name=attribute_escape( $cat->name);
$link=get_category_link( $cat->term_id );
$desc=$category->description;
$output.=$before_list.'<a href="'.$link.'">'.$name.'</a>'.$desc.$after_list;
$count++;
}
And that's it!