Dipende da quanto sono complesse le parti in gioco. Un footer e un header di solito sono molto semplici, con pochissime query, quindi include o require potrebbero bastare ed essere sufficienti.
Se invece la gestione di queste parti diventa complicata per via di parametrizzazioni molto spinte (es. ogni utente ha un suo menù, un so header, un suo footer eccetera) potrebbe valere la pena usare altre tecniche che in pratica eseguono i calcoli solo all'inizio e poi cambiano il contenuto, lasciando invariate le altre parti, come indichi anche tu.
Per poter fare quest'ultima, direi che ajax/xajax è la scelta ideale e per farlo puoi usare qualcosa del genere
codice:
<html>
<head>
</head>
<body>
<div id="contenuto_statico">
bla bla bla
</div>
<div id="contenuto_dinamico">
ble ble ble
</div>
</body>
</html>
Dentro il div contenuto_dinamico inserisci tutta la parte "dinamica" del sito e i vari link sono tutti del tipo
codice:
testo link
Questo però ti obbliga a dover strutturare tutto in modo da funzionare con ajax e non è semplicissimo (anche se fattibilissimo...ho costruito un intero gestionale che gira solo con ajax).