Hum. Nop. Media queries no es lo adecuado para esto.
Este tipo de cosas es por detección de la altura a la que está el elemento con respecto del alto original de la página, por lo que hay que detectarlo con JavaScript.
Básicamente el JavaScript detecta que el scroll ya se realizó y entonces agrega un class nuevo al elemento (por ejemplo header).
En ese Header con un class nuevo ahora se aplican estilos diferentes.
Para que tengan transición puedes jugar por ejemplo "colapsando" los elementos cambiando la altura, y haciendo transiciones css.
Una librería que en especial me gusta es esta:
http://imakewebthings.com/waypoints/
Para que veas ejemplos:
https://www.google.com.mx/search?q=w...ts+animate+css
En estos casos están usando una librería llamada animate.css pero el concepto es lo que comento arriba. Agregar un class. Para lo de "siempre visible" recuerda agregar en ese class nuevo un position=fixed.