The trick is very simple and easy to do. Using the view.phtml file of your theme that can be found on app/design/frontend/your-package/your-theme/template/catalog/product/view.phtml. Open it and add the following code:
foreach ($cats as $category_id) {
$_cat = Mage::getModel('catalog/category')->setStoreId(Mage::app()->getStore()->getId())->load($category_id);
echo $_cat->getName();
}

