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.