Si usas PHP puedes hacer un require en cada pagina.
Dependiendo del servidor web que uses puedes usar funciones de precompilador, en IIS sería:
Código HTML:
<!-- #include file="ruta/nombre.ext" -->
Si no, puedes incluir el menu usando AJAX y si no tiene formularios o algun objeto DOM que requieras llamar mediante funciones JS puedes incluirlo rapidamente mediante "innerHTML"