I'm a newbie so I maybe I'm wrong, but I was just asking about menus/navbars yesterday and here's what I learned.
WP 3.0 now has menu building capabilities accessible through the admin:
Appearance > menus. It allows for multiple menus.
I designed my own theme so I had to "enable" menus. What you might have right now is the message that your theme isn't set up to work with the menus admin or words to that effect. That's what I had.
I followed the instructions from here:
and added the code to my functions.php and to relevant templates.
I'm building one main menu, then have a secondary menu for just blog related items (my site is a business site with a blog, not a blog with some static pages). So my second menu is going into a second sidebar just on blog related pages. I've used widgets for that menu and it's interacting just fine with my main menu.
Now I have to figure out the proper way to use the options IN the admin - menu, to style my navbar, but that's another issue. I'll be posting that question.
Hope this gets you started!