Hi there, I can see using Firebug – a very handy tool for web development – that the navigation bar has the class site-navigation. That means you can apply a new background colour to it with some CSS like this:
.site-navigation {
background-color: #bb00bb;
}
Change the colour code to whatever shade you like.
The other class on the menu – main-navigation – has a CSS gradient being applied, so bear that in mind. If you want to remove the gradient you’ll need to modify that class too.
Here are some helpful resources for customizing your CSS:
https://dailypost.wordpress.com/2013/07/25/css-selectors/
http://dailypost.wordpress.com/2013/06/21/css-intro/
http://en.support.wordpress.com/custom-design/how-to-find-your-themes-css/
Keep in mind that CSS added through your custom CSS plugin overrides the existing CSS. Because of the way CSS inheritance works, sometimes you may need to add !important just before the semicolon to have it take effect on your theme.
Good luck!