you have 2 options. For both of them you have to edit app/design/frontend/{interface}/{theme}/template/catalog/product/list.phtml
1. Add the category (categories) link(s) for all the products in any list (search results included). Keep in mind that any product can be in one or more categories (or none).
At the top of the file add this:
<?php $_category = Mage::regsitry('current_category');?>
<?php if ($_category) : ?>
<a href="<?php echo $_category->getUrl();?>"><?php echo $_category->getName();?></a>
<?php endif;?>
2. At the top of the file add this:
<?php $_categories = array();?>This will work as some kind of cache.
Now below the $_product item (inside the foreach) add this
<?php foreach ($_product->getCategoryIds() as $categoryId) : ?>
<?php if (isset($_categories[$categoryId])) : ?>
<?php $_category = $_categories[$categoryId];?>
<?php else:?>
<?php $_category = Mage::getModel('catalog/category')->setStoreId(Mage::app()->getStore()->getId())->load($categoryId);?>
<?php $_categories[$categoryId] = $_category;?>
<?php endif;?>
<a href="<?php echo $_category->getUrl()?>"><?php echo $_category->getName();?></a>
<?php //if you want only the first category link add a break here; ?>
<?php endforeach;?>
This second method covers all the cases but it's a little bit slower than the first one.
