beh io ora non so che cosa usi come modulo ajax, io ogni tanto uso il dojo toolkit che è davvero fantastico..cmq io ti faccio un esempio generico che cmq vale sempre anche con moduli ajax perchè non sono altro che estensioni dei tag normali...

Codice PHP:
<?php
   $nazione = $_POST['nazione'];
   $regione = $_POST['regione'];
   if ($nazione) $id=1;
   if ($regione) $id=2;
?>
<html>
<head><title></title></head>
<body>
<form id="test" method="post" action="<?=$_SERVER['PHP_SELF']?>">
  <select name="nazione" size="1" onchange="document.forms[0].submit()">
    <option value="1">Italia</option>
    <option value="1">Francia</option>
    <option value="1">Spagna</option>
  </select>
  <? if ($id==1) { // $nazione è stata selezionata ?>
  <? 
     if ($nazione==1) $regioni = array('Liguria', 'Piemonte', 'Lombardia');
     if ($nazione==2) $regioni = array('Provenza', 'Pyrenees', 'Loira');
     if ($nazione==3) $regioni = array('Andalusia', 'Costa Brava', 'Galizia');
  ?>
  <select name="regione" size="1" onchange="document.forms[0].submit()">
    <?
       for ($i=0; $i<count($regioni); $i++)
          echo "<option value=\"$i\">".$regioni[$i]."</option>";
    ?>
   </select>
  <? } ?>
  <? if ($id==2) { // $regione è stata selezionata ?>
  <? // ecc ecc ?>
</form>
</body>
</html>
questo è il metodo standard in PHP, poi dipende dal framework ajax che usi come implementarlo...