A ver...
Puedes hacer dos cosas:
Una, en dós páginas distintas (lo más simple), que en una página seleccione el país, y mediante GET o POST pases esa variable a la otra página,que segun la opcion seleccionada, de unos resultados u otros.
Te pongo más o menos el código:
(Página 1, con los páises)
Código HTML:
<form name="paises" action="pag2.php" method="GET">
<input name="pais " type="select".... //Aqui los select con los páises>
<br><br>
<input name="Submit" type="Submit" value="Siguiente">
</form>
Esto dará una url como esto:
http://tudominio.com/pag2.php?pais=España
Ahora, en pag2.php, recojes esa variable, haces la sentencia a la bd, y en otro select muestras las ciudades correspondientes a ese país:
Código PHP:
$pais = $_GET['pais']:
//Aqui la conexión a la db
$link = mysql_query ("SELECT ciudad FROM ciudades WHERE pais='$pais'")
//Lo metes en un array, y lo muestras en el select de un nuevo form, haciendo un un while hasta que haya mostrado todas las ciudades.
Y la otra opción, es lo mismo pero usando solo una página, para lo que tendrás que hacer por javascipt, o alguna función php, que en cuento seleccione el país, se autoactualice la página, haciendo la sentencia a la db.
Y si esto no te vale...no se que más decirte :S
Un saludo y suerte!