Doesn't this belong in a "Programming" forum
You really have 3 options.
1. enable server side includes (.shtml) in apache and put your menu in a file and call the file from each page
2. install PHP (if you need help let us know) and make a php include file, then call that file on each page.
3. useing Perl to search and replace. This will work for now but will get very cumbersome as the site grows.
IMHO, the PHP route is the best. It provides you more flexability in the long run plus you can add a database very easially. PHP is fairly easy to install, php.net has some great tutorials and I am also fairly familiar with installing both PHP and apache.
If you want some examples on how to make a PHP include file or of PHP code just PM me.