En PHP tendrías que recargar toda la página para hacerle llegar el dato de tu primera selección de tu primer select y que se tome como condicional para el segundo select (ademas de pre-establecer los valores anteriores (el que se seleccionó) en el primer select...)
Para hacer esto sin "recarga de página aparente" (se recarga igualmente .. pero suele ser un iframe/frame oculto y se gestiona todo por javascript) puedes ver técnicas de "remote scripting" como los ejemplos que tienes en este sitio:
http://www.ashleyit.com/rs/main.htm
Un saludo,