How do I add images to my theme?

I'd like to add images and change my header design to similar to this site http://fitness.sitegap.com/.
How do I go about that? What type of plugin do I need? How can I change the design of the header?

Can someone give a name of a free website where I can find a header?