Solución:
Le pregunté a AWS Support y la respuesta fue que, por el momento, ELB no puede agregar encabezados HSTS en las solicitudes de los clientes. Entonces, decidí encontrar una solución usando mi servidor Apache. Aquí está la solución que encontré:
El HSTS RFC establece que
Un host HSTS NO DEBE incluir el campo de encabezado STS en las respuestas HTTP transmitidas por transporte no seguro.
Lo que hice entonces fue configurar el encabezado DESPUÉS la redirección http => https en Apache. Dado que esta redirección tiene la bandera [L], eso significa que la redirección 301 no incluirá el encabezado, pero cualquier solicitud https sí. Mi configuración de apache se ve así:
<VirtualHost *:80>
...
#http=>https
RewriteCond %{HTTP:X-Forwarded-Proto} =http
RewriteRule . https://%{HTTP:Host}%{REQUEST_URI} [L,R=permanent]
#hsts
Header set Strict-Transport-Security "max-age=31536000"
Si está trabajando con Apache 2.4+, es posible que esté familiarizado con las expresiones y las directivas <If>, <ElseIf>, y <Else>.
Tengo una configuración compleja entre los entornos de desarrollo, preparación y producción, por lo que confío en el [L] bandera con el RewriteRule simplemente no lo haría por mí.
Esto me llevó a la siguiente solución, que coloqué en mi .htaccess:
<IfModule mod_headers.c>
<If "%{REQUEST_SCHEME} == 'https' || %{HTTP:X-Forwarded-Proto} == 'https'">
Header set Strict-Transport-Security "max-age=31536000"
</If>
</IfModule>
Funciona mejor en mi entorno y creo que es más confiable para cumplir con el RFC.
Podrías dejar caer el "%{REQUEST_SCHEME} == 'https' parte si nunca llega a sus instancias directamente, pero eso es parte de mi proceso de depuración en mis entornos de desarrollo.
Muchas gracias a Pedreiro por indicarme la dirección correcta para las especificaciones reales del HSTS RFC.