For The Nav Bar, You can add it in the: Template/overall_header.html of your style folder.
the ideal place to add the nav bar will be before the breadcrumb (just like above in phpbb forum), so find and add your nav bar code before
but of course you can move it through the overall_header as you wish.
for the header, I don't know what you mean by changing the header? if the logo you can change it depending on your style by replacing the logo image with your own. or you mean something else?