Pai css-ul este clar.. il pui separat si il incluzi in fiecare pagina, ca ai nevoie de el... oricum

Pentru meniu in schimb, exista varianta sa il faci cu javascript... dar nu este indicata din mai multe motive:
- js-ul se executa la client si depinde de setarile browserului. daca js este disabled.. meniul tau nu va aparea.
- meniul nu va fi vazut de motoarele de cautare.

In js poti sa ai o metoda de genul

Cod:
function showMenu() {
    document.write("<ul>");
    document.write("<li>");
    ...
}
metoda care o apelezi pe evenimenul onload din body
<body onload="showMenu()">

Dar cea mai buna varianta ramane php-ul... este mult mai flexibil.
Poti sa iti faci meniul separat.. si sa foloseti include sau require ca sa il afisezi... Totul se executa pe server si este vizibil motoarelor de cautare.