IMHO, there are some major problems with frames, namely that they make bookmarking individual pages difficult and that search engine robots won't always be able to easily index them.
I prefer to use include() statements with PHP. You would place the entire header portion in a file (such as header.htm) and then "include" it at the top of the page with
<?php
include('header.htm');
?>
Put this include() statement at the top (or wherever you want the header information to appear) of the page.
That way you have to only update one file (header.htm) and all the other pages will automatically be updated.