First thing you will want to do is creat a local path because we're going to override core Magento functionality. So let's make the following directory (including any required paths to make the directory)
app/code/local/Mage/Sitemap/Model/
If you're doing this from a Shell.
mkdir -p app/code/local/Mage/Sitemap/Model/
Then copy over the core file like so
cp app/code/core/Mage/Sitemap/Model/Sitemap.php app/code/local/Mage/Sitemap/Model/
Now we jump into the code. There are three $date variables, one each for the categories section, products section and cms pages section. We're going to replace them with the following code.
At around ~Line 158 replace $date with:
substr(Mage::getModel('catalog/category')->load($item->getId())->getUpdatedAt(),0,10),
At around ~Line 176 replace $date with:
substr(Mage::getModel('catalog/product')->load($item->getId())->getUpdatedAt(),0,10),
At around ~Line 193 replace $date with:
substr(Mage::getModel('cms/page')->load($item->getId())->getUpdateTime(),0,10),
Regenerate your sitemap.xml from Magento's admin or your cron schedule and test it's working ok.