Make a new document. For this tutorial I am using 800x40 with a resolution of 72 pixels/inch with Colour Mode set to RGB Colour 8 bit.

Make a box that takes up most of the area, but leave around 5 pixels space at the bottom and fill with a gradient of #FFFFFF to #DDDDDD from top to bottom of the selection to make this:

Now out of the 5 pixels you left select the middle 3 using the single line marquee tool or by using the rectangular marquee tool.

Create a new layer and fill this with #006699 and set the opacity of this layer to 50%

Now we have the background for our navigation bar. Select the vertical single line marquee tool and draw a line anywhere vertically down your nav bar. Create a new layer and fill it with #000000. Then delete everything on and below the blue bar to get this.

Get the rectangular marquee tool and make a small selection at the top like this:

Go to Select » Feather » Set to 10px then press OK. Press the Delete key around 10 times and set the layers opacity to 50%.

Add all your text in for your links and duplicate the spacers to go in between the links

Select the vertical single line marquee tool again and click on one of the spacers to select the whole line.

Now click Layer 2 which is your blue bar and press Delete then move the bar 1 pixel to the left then delete then 2 pixels to the right then press delete.

You now have a complete navigation bar.