Bueno, finalmente conseguí hacerlo. Dejo el código por si a alguien le sirve:
Código HTML:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Documento sin título</title>
<script language='javascript' src="popcalendar.js">
</script>
<script>
function cambiar(que){
if(document.form1.select.selectedIndex==0){document.getElementById('provincia').innerHTML='';return;}
bsas=new Array('Aeropuerto Ezeiza','Bahía Blanca','Bahía Blanca Apt','Escobar','La Plata','Lobos','Mar del Plata','Mar del Plata Apt','Pergamino','Pilar','Pinamar','Rojas','Villa Gesell');
capital=new Array('Aeroparque Jorge Newbery','Buenos Aires, Centro','Belgrano','Palermo','Puerto Madero');
chaco=new Array('Resistencia Apt');
chubut=new Array('Comodoro Rivadavia, Centro','Comodoro Rivadavia Apt','Esquel Centro','Esquel Apt','Puerto Madryn Centro','Puerto Madryn Apt','Trelew, Centro','Trelew Apt');
result=eval(que);
cadena='';
for(i=0;i<result.length;i++){
cadena+="<option value=\""+result[i]+"\">"+result[i]+"</option>";
}
document.getElementById('provincia').innerHTML="<select name=\"select2\">"+cadena+"</select>";
}
</script>
</head>
<body>
<form name="reserva" method="post" action="">
País
<select name="zona">
<option selected value="">
<option selected value="argentina">Argentina
<option value="resto">Resto del Mundo
</select>
<p>Provincia
<select name="select" onchange="cambiar(this.value)">
<option selected value=""></option>
<option value="bsas">Buenos Aires</option>
<option value="capital">Capital Federal</option>
<option value="chaco">Chaco</option>
<option value="chubut">Chubut</option>
</select>
<div id="provincia" style="display:inline"></div>
<p>Tipo de Auto
<select name="liste1" size="1">
<option selected value="">
<option value="economico.php">Económico
<option value="http://www.yahoo.com.ar">Familiar
<option value="http://www.yahoo.com.ar">Grande
</select>
</p>
<p>Fecha de Alquiler
<input name="fecalq" type="text" id="fecalq" onclick="popUpCalendar(this, fecalq, 'dd/mm/yyyy');"/>
</p>
<p>Fecha de Devolución
<input name="fecdevol" type="text" id="fecdevol" onclick="popUpCalendar(this, fecdevol, 'dd/mm/yyyy');"/>
<p><input type="button" value="Buscar"
onClick="if (form.liste1.selectedIndex != 0)
location = form.liste1.options[form.liste1.selectedIndex].value;
else
alert('Por favor, seleccione una opción')">
</p>
</form>
</body>
</html> Y acá está el formulario: http://www.elegircarilo.com.ar/prueba.php
El único tema que me quedó es que me gustaría poner un texto a la izquierda del menú de lugares que depende del primero. ¿Alguien tiene idea de cómo hacerlo?