Efectivamente, se puede hacer desde PHP.
La diferencia entre ambas soluciones (JS y PHP) radica en que con PHP la página debe volver a cargarse cuando seleccionas una opción de tu primera lista, y en javascript no.
Cuando usar cada una? depende de lo complejo de tus consultas secundarias, y de qué tanto estés dispuesto a depender de que el usuario tenga instalado javascript.
En este momento no tengo mucho tiempo disponible, pero te voy a dar la idea general...
Cuando se carga originalmente tu pagina, aparecerá llena solo la primera lista, y en la segunda aparecerá algo así como "--primero selecciona una ciudad--"
Y tu script tendrá mas o menos esta estructura:
<select name="ciudades" onchange="this.form.submit()">
Aqui tus opciones principales (Ciudades en mi ejemplo)
</select>
<select name="colonias">
<?
if (isset($_POST[ciudades])) { //Si se ha seleccionado una ciudad
/* creas tu consulta y generas la lista de colonias */
/* por ejemplo "SELECT * From colonias where ciudad=".$_POST["ciudades"]" */
} else {
echo "<option>--Primero selecciona una ciudad--</option>
}
?>
</select>
Got it??