Upload your header image into templates/images.

Edit header.tpl file and add the following code in to first table (After <div id="hd"> the first <table>)

style="background-image: url({$baseurl}/templates/images/header.gif)"