Changing the header colour on WordPress Parallax theme

You need to edit the style.css file.  Simply search for the id,   navigation_menu.container-full-width and change background-color to the hex value colour you want.
#navigation_menu.container-full-width {
border-bottom: 4px solid #b2b3b2;
background-color: #2E3233;
/*    background-image: url(images/bg.jpg); */

In this example the background image has been neutraised by commenting (rather than deleting) and and the background color changed to #2E3233