In your local.xml
file add the below code to add a custom header to the checkout page
<checkout_onepage_index>
<reference name="root">
<block type="page/html_header" name="header" as="header" template="page/html/your_new_header_file_name.phtml"/>
</reference>
</checkout_onepage_index>
Now create a new_header.phtml
in app/design/frontend/default/default/template/page/html
and add the custom header contents in this file. Now update your new header file name in the above template field.
You can replace default/default
with your_package_name/your_theme_name