There is no out of the box way of doing this, but you can trick magento into doing this.
You can create a hidden attribute called category_names
that is seachable but not displayed in the frontend.
Then create an observer for the catalog_product_save_before
where you take all the category names from the associated categories and place them in this field.
Something like this (untested):
public function setCategoryNames($observer)
{
$product = $observer->getProduct();
$categoryIds = $product->getCategoryIds();
$storeId = $product->getStoreId();
$categories = Mage::getModel('catalog/category')->getCollection()
->setStoreId($storeId)
->addAttributeToFilter('entity_id', $categoryIds)
->addAttributeToSelect('name');
$names = array();
foreach ($categories as $category) {
$names[] = $category->getName();
}
$product->setCategoryNames(implode(' ', $names));
}