How do I change the header image in Plone?

You should be in the Zope interface. Go to /portal_skins/plone_images/logo.jpg. Customize, and upload your header image.

Ta da!