You can try to create an observer in a module, preferrable your own module in the local code pool:

    <!-- app/code/local/Mymodule/etc/config.xml -->
    ...
    <global>
        <events>
            ...
            <sales_order_place_after>
                <observers>
                    <clear_session>
                        <class>Mymodule_Model_Observer</class>
                        <method>clearCheckoutSession</method>
                    </clear_session>
                </observers>
            </sales_order_place_after>
        </events>
    </global>
    ...

Don't know how this works? See here:

http://www.magentocommerce.com/wiki/5_-_modules_and_development/0_-_module_development_in_magento/customizing_magento_using_event-observer_method


Once you declare the observer, build it out:

    <?php

    // app/code/local/Mymodule/Model/Observer.php

    class Mymodule_Model_Observer 
        extends Varien_Event_Observer
    {

        public function clearCheckoutSession()
        {
            Mage::getSingleton('core/session')->clear(); // Or whatever you want to clear
        }

    }

You'll want to customize this to your needs, obviously. And put some verification checks in there as well.

**EDIT:** As per laketuna's suggestion, I changed the target event to `sales_order_place_after`, as it seems to be the most reliable one to observe.