Creating A Nav Bar

I am working on creating a blog for our company and have picked a theme I like, but i need to create a new menu that doesn’t exist as apart of the theme. The theme has menus as buttons on the right and left of the header. I would like to create a stationary navigation bar either above or below the header image. Preferably above. I honestly have no idea how to go about this. Ideally I would like our logo on the left and just a few linked pages on the right. Any suggestions as to plugins or tutorials would be greatly appreciated.