Welcome to part one of my two part tutorial, This part covers the designing of the header and navigation in Photoshop, and part 2 covers the coding of the header and navigation.
Start off by making a new document 800 PX wide and 350 PX Tall. Fill the background in with #4a4a4a
Now go the rectangular marguee tool, Set it to use a fixed size of 800 X 100 Pixels
To use a fixed size, Go to the drop down box on the horizontal toolbar and select Fixed Size for your style. Create a new layer (CTRL + SHIFT + N) (Name it Header if you want) Fill it in with white, Now deselect (CTRL + D) and go over to your layer palate and right click header, and select blending options, Apply these layer styles to it:

Here is what mine looks like:

Click for full screenshot
Now make a fixed selection with the rectangular marguee tool of 800 X 45 , Create a new layer (Name it Navigation) and fill it in with white. Now go to your blending options and apply the following layer styles:

Now we will make some navigation spacers, Zoom in on your navigation, Go to the line tool and use the default settings now make a black line from the top of your navigation to the bottom of it, Turn the opacity on the layer down to 30%, Do this again just this time just use white for the color, and put the opacity down to 10%. Now move the lines up against eachother, Here is what mine looks like:

Now zoom back out and have a look. Now we will make the rollover for the navigation, Make a selection from one spacer to the other and make it 44px tall (So the stroke on the navigation will still show above it.) Here is my selection:
and fill it in with white, Apply these layer styles to it:

There you have it, Add some text to the navigation and yours and the navigation is done. Here is what mine looks like:

Click for full screenshot
Now we will add a search form and button, Use the rounded rectangle tool with a radius of 5px to make a shape like this:

Click for full screenshot
Apply the same layers styles for this that you did to the navigation's background (Right click the navigation background in the layers palate and select copy layer style, Than right click the shape's and paste the layer style.) Add an input box, and the search is done. Here is what my final result looks like.

Click for full screenshot
This concludes part 1.
Click here to go to part 2 which covers the CSS coding of the header and navigation.
Download the .psd