Product sorting on Date

// app/code/core/Mage/Catalog/Model/Config.php
public function getAttributeUsedForSortByArray()
{
    $options = array(
        'position'  => Mage::helper('catalog')->__('Position'),

        // HERE IS OUR NEW OPTION
        'created_at' => Mage::helper('catalog')->__('Date')
    );
    foreach ($this->getAttributesUsedForSortBy() as $attribute) {
        /* @var $attribute Mage_Eav_Model_Entity_Attribute_Abstract */
        $options[$attribute->getAttributeCode()] = $attribute->getStoreLabel();
    }

    return $options;
}

It is not so easy, if you are not into modifying core files. In that case you must create this bunch of files:
app/etc/modules/Stackoverflow_Catalog.xml

<?xml version="1.0"?>
<config>
    <modules>
    <Stackoverflow_Catalog>
        <active>true</active>
        <codePool>local</codePool>
        <depends>
            <Mage_Catalog />
        </depends>
    </Stackoverflow_Catalog>
</modules>
</config>

app/code/local/Stackoverflow/Catalog/etc/config.xml

<?xml version="1.0"?>
<config>
<global>
    <models>
        <catalog>
            <rewrite>
                <config>Stackoverflow_Catalog_Model_Config</config>
            </rewrite>
        </catalog>
    </models>
</global>

app/code/local/Stackoverflow/Catalog/Model/Config.php

<?php
class Stackoverflow_Catalog_Model_Config extends Mage_Catalog_Model_Config {
public function getAttributeUsedForSortByArray()
{
    $options = parent::getAttributeUsedForSortByArray();
    if (!isset($options['created_at'])) {
        $options['created_at'] = Mage::helper('catalog')->__('Date');
    }
    return $options;
}
}