You can achieve this with a layout update for your cart page (either via your custom module, or in your themes local.xml
- i.e. app/design/frontend/{theme}/{theme}/layout/local.xml
- by removing the particular area inside a <checkout_cart_index>
node (and/or inside a <checkout_onepage_index>
node if you'd like to hide parts from the checkout as well).
For removing the complete header add this inside the layout XML file as described above:
<layout>
<checkout_cart_index>
<remove name="header"/>
</checkout_cart_index>
</layout>
This should lead to something like that:

*) Please note that your customer will have a hard time on finding back to where they came from if you remove the whole header!
If you'd just like to remove the categories (i.e. the top navigation) you can refer to the same like so:
<layout>
<checkout_cart_index>
<reference name="topMenu">
<remove name="catalog.topnav" />
</reference>
</checkout_cart_index>
</layout>
This should lead to something like this:

The same concept applies on the <checkout_onepage_index>
node. Just add the same structure for this node as well.
This should be working as long as your current theme is respecting given layout rules specified by Magento.
You can check for example your themes (i.e. app/design/frontend/{theme}/{theme}/layout/.page.xml
) and the base' (i.e. app/design/frontend/base/default/layout/.page.xml
) default page layout definition to see what block are called (where/how).
Some good read on this topic can be found for example here: