Magento has an "upsell" feature, where you specify other products to show as a list on the product page in a "you might also be interested in.." manner.

By default you have to select the upsell products for each product individually, but it's built in a way that you can extend it with your own logic.

So if you don't already use upsells, this is the way to go:

Observe catalog_product_upsell

Create an observer for the catalog_product_upsell event. It uses the product collection provided by the product's category.

In the following example I keep existing upsell products if there were any manually configured and fill them up with products from the same category. Adjust the logic as needed:

use Mage_Catalog_Model_Product as Product;
use Mage_Catalog_Model_Product_Link as RelatedProduct;
use Mage_Catalog_Model_Resource_Product_Link_Product_Collection as RelatedProductCollection;

class IntegerNet_AutoUpsell_Model_Observer
{
    /**
     * @see event catalog_product_upsell
     * @param Varien_Event_Observer $observer
     * @throws Mage_Core_Exception
     */
    public function fillUpsellCollection(Varien_Event_Observer $observer)
    {
        $collection = $observer->getCollection();
        if ($collection instanceof RelatedProductCollection
            && $collection->getLinkModel()->getLinkTypeId() === RelatedProduct::LINK_TYPE_UPSELL
            && $collection->count() < $observer->getLimit('upsell')
        ) {
            $this->addItemsFromCategory($collection, $observer->getLimit('upsell') - $collection->count(), $observer->getProduct());
        }
    }
    protected function addItemsFromCategory(RelatedProductCollection $collection, $numberOfItems, Product $product)
    {
        /** @var Mage_Catalog_Model_Resource_Product_Collection $productsToAdd */
        $productsToAdd = $this->_getProductCategory($product)->getProductCollection();
        $productsToAdd
            ->addStoreFilter()
            ->addIdFilter(array_merge([$product->getId()], $collection->getAllIds()), true)
            ->setVisibility(Mage::getSingleton('catalog/product_visibility')->getVisibleInCatalogIds());
            ->addMinimalPrice()
            ->addFinalPrice()
            ->addTaxPercents()
            ->setPageSize($numberOfItems)
            ->addAttributeToSelect(Mage::getSingleton('catalog/config')->getProductAttributes())
            ->addUrlRewrite();
        foreach ($productsToAdd as $product) {
            $collection->addItem($product);
        }
    }

    /**
     * @param Mage_Catalog_Model_Product $product
     * @return Mage_Catalog_Model_Category
     */
    protected function _getProductCategory(Product $product)
    {
        $category = $product->getCategoryCollection()
            ->setPageSize(1)
            ->getFirstItem();
        return $category;
    }
}

Some parts that I'd like to highlight:

->addIdFilter(array_merge($product->getId(), $collection->getAllIds()), true)

This excludes the product itself and the products that are already manually defined as upsell products (as stated above, I leave them and only fill the blanks)

->addMinimalPrice()
->addFinalPrice()
->addTaxPercents()
->addAttributeToSelect(Mage::getSingleton('catalog/config')->getProductAttributes())
->addUrlRewrite();

This prepares the product collection to load the necessary data to display prices, the product link and any attributes configured as "used in product listing", but not more.