Todo depende de la complejidad de tu web.
En cuanto a cabecera común, deberías usar por ejemplo php, y con un simple
Y que también te serviría para crear contenido.
Si quieres mantener la loca idea de no "actualizar o recargar" tu web (algo que se lograba con los marcos) deberías incursionar en ajax o similares.
Digo loca idea, porque a mi parecer eso tenía sentido cuando las conexiones eran muuuy lentas, además que, a menos que sea algo muy interactivo, o que tu web sea muuuy pesada, no le veo mayor inconveniente a recargar o cargar una nueva página.
Sobre la estructura de la página, es decir el html, pues no es más que reemplazar los frames por div o mejor aún utilizar las etiquetas de html5, digo, si te vas a renovar, que mejor que aprovechar lo más nuevito.
Claro que además tendrás que aplicarle estilo, u ordenar los elementos donde quieras que vayan, con css.
Saludos