It's because products can be attached to multiple categories. In your situation, when you visit a product page referred from a category page, your session has category information. But if you visit directly product page, Magento can not know which category you came from, so it can not show you a specific category, because your product can have multiple categories.
But in your situation, if your products are attached only one category, you can use this code, it shows first category name of product;
$categoryIds = $_product->getCategoryIds();
if(count($categoryIds) ){
$firstCategoryId = $categoryIds[0];
$_category = Mage::getModel('catalog/category')->load($firstCategoryId);
echo $_category->getName();
}