Changing Navigation Menu Bar Background Color to image

Hello,

I am trying to replace the Navigation menu bar and page footer background color with an image. How do I do that, if I’m using the Twenty Twelve Theme? or is there a better theme to perform that? I’m still in the early stages of learning wordpress. An example of what I’m trying to do is on the following website:

http://www.wits.ac.za

Also, how to I put that search box to the top right corner? Thank you in advance.