This IS possible.
Well, it is possible if you put the PHP header into PHP pages. HTML pages can't contain PHP.
Create one PHP file containing the header. It would be something like:
echo "a bunch of stuff for my header";
?>
Upload this file onto your server as /include/header.php or something.
Then include this in all your PHP pages:
require_once getenv("DOCUMENT_ROOT")."/include/header.php";
//the rest of the page follows
?>
You could use "include" instead of "require_once". They both include other PHP files. I use "require_once" because including the same file twice with "include" will cause a bug. It's basically just a stupid syntax issue.
I do this on my website, though I use functions in my header.php to output different headers and various other things.
Go to http://orbitalcows.com/ . That banner at the top of most pages is created by the header file. I also set the background and text colors that way instead of using CSS.