All the methods you've mentioned do work, but they do have their pros and cons however.
Obviously, using just html/css creates a lot of redundancy, but there are no compatibility issues (not realistically anyways).
PHP, being a server-side language, also has little to no compatibility issues since the work is done by the server, not the guest. And includes are a nice handy way of keeping your site up to date, and with more functionality than just html. But, like you say, each page will (re)load completely. If your issue with that is loading time, keep in mind that much of it will be cached.
Keep in mind though that all of this may change as html5 starts to become prevalent. I haven't had an excuse to work with it myself yet, but from the samples and documentation that are floating around it seems that html5 will be able to do much of what JS is used for today. Hard to say what kind of affect that will have.