General Options -> Sources -> Search in Terms (categories, tags)
If you need to look for phrases in categories or other terms and return the related custom posts, then you should turn on this option.
Please not that this option is extremely resource heavy! Sites with lots of posts/products will most likely experience higher delays in ajax search. In case of performance issues, please consider using the second solution.
Index table (submenu) -> General options -> Index taxonomies
If you are using the index table engine, you can choose which taxonomy terms to index along with the post types you have choosen.
Please note that this solution only works if you use the index table engine. You can read more about using it here.
Tags: search in categories, search in category, search in tags, category as result, categories as results, terms as results, return categories, return tags, return taxonomy terms