I use PHP for dynamic web pages. I don't know how much you know about PHP, but I have a menu on the left that appears on all pages (like on this site). The side menu is actually a separate HTML file. When the page is accessed, the server sticks the side menu into the page thanks to PHP code. It then sends the assembled page to your browser as though it was always a single file.
My ISP's web hosting doesn't support PHP, so it doesn't put the menu in.
The alternative is to use frames (which suck badly) or to make the menu part of every page (which means updating every file just to make a change to the menu - way too much work).
I can probably find some free hosting when I get motivated enough.

It's less than 1MB.