Basta usare include per quello che dici tu.

Esempio

index.php

<html>
<head>
</head>
<body>
<!-- Menu -->
<?php include 'menu.php'; ?>

<!-- Qui il resto del body -->

</body>
</html>

Il menù lo includi in quel modo in tutte le pagine, cosi modifichi solo la pagina menu.php

La pagina menu.php dovrà contenere solo il menu e quindi con i div e i vari tag, senza i tag <html> o <body>