Bueno, existen dos (o mas) forma de hacerlo, una de ellas con Javascript y otra con PHP (o cualquiera del lado del servidor)..
La primera la puedes ver en las FAQ de Javascript, y es esa la que puede hacerlo sin recargar.
La segunda te la platico en PHP, ya que este es el foro en el que estamos:
Al hacer un select envias la forma, ya sea con un boton o con javascript (onChange)...
Al recibir la variable post en el script, "generas" el nuevo select de ciudades con tu BD.
Y asi respectivamente...
