The background of the navigation menu is done with images. if you look in the ‘style-skin-5.css’ stylesheet, on line 120 or thereabouts you’ll see this chunk of CSS…
/* top */
#Top { background-image: url("images/skins/skin-5/topMenu-Repeat.png"); } /* top menu bg */
#TopContainer { background-image: url("images/skins/skin-5/topMenu-Middle.png"); }
Those are the two images you’d need to change to change the background of the navigation menu.
If you use the Internet Explorer, Chrome or Safari browsers you can use their built-in developer tools to point at and “inspect” elements on a web page to find out what styles they use. You can even tweak the styles live to experiment with any changes you might fancy. If you use Firefox then there is an add-on named Firebug you can install which gives that browser the same functionality as the developer tools built into the other browsers.
If you need to learn how to use CSS then I can recommend this site → http://www.w3schools.com/css/