Select Dependientes

Para hacer que 2 selects dependan uno de otro no podrás hacerlo de forma automática si recargar la página en PHP, ya que para que se ejecute el código PHP se necesiat una petición al servidor y por tanto una recarga de página.
Si lo que quieres es generar automáticamente el segundo select debe ser en un lenguaje de programación que se ejectue en el cliente ya sea javascript, vbscript o jscript. Yo recomiendo que lo hagas en javascript.
El funcionamiento es algo complejo si no estas familiriadizado con la interacción php y javascript
En resumen lo que debes hacer es general código javascript dqeu se ejecutara en el cliente. Primero generas el primer select con todos los paises. Después con código php generas un array en javascript que serán las ciudades del país una buena forma seria crear para cada ciudad una variable que quedaría más o menos así
array_espana[0]="Madrid";
array_espana[1]="Barcelona;
array_francia[0]="Paris";
array_francia[1]="Lyon";
Una vez tienes esto, lo que debes hacer es utilizar el método onchange del select de países el cual llamara a una función que rellenara el segundo select de ciudades.
Un codigo de ejemplo seria este :
<script language="JavaScript">
var array_espana = Array();
var array_francia = Array();
array_espana[0]="Madrid";
array_espana[1]="Barcelona";
array_francia[0]="Paris";
array_francia[1]="Lyon";
function rellenar_ciudades(pais)
{
if (pais.length==0) return;
array_temp = eval("array_"+pais);
select = document.dos_selects.ciudades;
select.length=0;
select.length++;
select.options[select.length-1].text="Seleccione la ciudad";
select.options[select.length-1].value="";
select.options[select.length-1].selected=1;
for(i=0;i<array_temp.length;i++)
{
select.length++;
select.options[select.length-1].text=array_temp;
select.options[select.length-1].value=array_temp;
select.options[select.length-1].selected=0;
}
}
</script>
<form name='dos_selects'>
<select name='paises' onchange='rellenar_ciudades(this.value)'>
<option selected value=''>Seleccione el pais </option>
<option value='espana'>España</option>
<option value='francia'>Francia</option>
</select>
<select name='ciudades'>
<option selected value=''>-Seleccione la ciudad </option>
</select>
</form>