I think there are a couple of solutions to your problem. I'm no expert
by any stretch of the imagnation, but I've asked enough questions here
that I think I should at least try to pitch in.
You might be able to use some kind of ajax functionality to load the
page contents while not having to reload the rest of the page. The
basics are really quite simple and you can find several tutorials
online. Basically, when somebody clicked on one of your links, your
XMLHttpRequest object could send that request to the webserver and
populate the main page content element with the new content. This
would keep you from having to reload the menu for each page.
You could also, possibly, save the menu object into the session object
and then just print it out on each page. You'd want to do a check to
make sure the menu exists on each paint though and create it if it
doesn't exist.
Really though, unless your menu is extensive, I'd suspect that just
rewriting the menu every time the page is loaded wouldn't cause
extensive performance issues.
Like I said, I'm no expert, just thought I'd chip in my .02¢.