I have no idea about anything GoLive (never had it, never used it); but in general, this is very simple to accomplish with a tiny amount of scripting in a language like PHP or ASP. Usually, you’d create a simple HTML file that contains only the HTML code for the navigation menu, and then you’d use PHP/ASP/etc. to include that file at the right point in your other pages. That way, it’s the same file being pulled up for all pages, and any changes you make to that file will automatically propagate.
A similar (though much less clean and ‘pretty’) solution exists in Dreamweaver, if I recall correctly. Something with making one page the ‘master’, and then only allow certain parts of it to be modified when you make individual pages based on this ‘master’ page. When you alter the master page, all the other pages are then simultaneously changed. I’m sure something similar must exist in GoLive, too.