Eccoti un esempio fatto con jQuery. Se hai dubbi chiedi!

codice:
<select id="rubrica_anagrafica_id_provincia" name="id_provincia" onchange="getComuniByIdProvincia()">
<option value="">-- Provincia --</option>
<option value="12">Agrigento</option>
</select>

<select id="rubrica_anagrafica_id_comune" name="id_comune">
<option value="">-- Comune --</option>
</select>

function getComuniByIdProvincia()
{	
	new Ajax.Request('paginatuoscript.php',
	{
		parameters: { id_provincia : $('rubrica_anagrafica_id_provincia').value },
		onSuccess: function(transport){			
                    $('rubrica_anagrafica_id_comune').update(transport.responseText);
    	},
    	onFailure: function(){ alert('Si è verificato un errore...'); }
  });
}


Ps.
l'esempio è migliorabile se dal tuo script ti fai restituire i dati in formato JSON piuttosto che in HTML