If I define a variable in header.php, how do I make it available to templates?

It the template is called via get_template_part(), then it is in a new variable scope. to access it, you have to use the global keyword in you template file:

global $foo;
echo $foo;

As header.php probalbly is also called in a function scope, you have to make sure there the variable is used in global scope when definig it:

global $foo;
$foo = 'bar';