If you haven't made any major changes to the template files you might want to consider switching over to using my Techozoic Fluid theme, it has many options that you can adjust, on of theme being the same color scheme as the khaki traveler theme. I also have any easy upload form for uploading and choosing new header images.

If you would still like to keep the khaki traveler theme you will need upload your image with ftp to the wp-content/themes/khaki-traveler/images/ folder then in the style.css look for this code.

Just change the header.jpg to whatever name your new header image is. The max dimensions for the image is 160px high by 1000px wide.