Tienes casi todo correcto, pero en el header.php ponlo así...
Código PHP:
<title><?php echo $titulo; ?></title>
Y si quieren algo un poquitín más completo... (Este lo que hace es que si te olvidas de declarar $titulo, pone un título generico para no dejarlo vacio...
Código PHP:
<title><?php if (isset($titulo)) { echo $titulo; } else { echo "Titulo generico"; } ?></title>
PD: También puedes o "debes" hacer lo mismo con las keywords y las description
Y por último, si tu sitio usa DB, esos valores podrías leerlos de la misma...