Rellenar Combos

[thi]

Hola a todos,

antes de nada decir que no tengo ni idea de Ajax.
El problema que tengo es que necesito rellenar unos combos de un formulario desde una base de datos, de forma que el primero se rellene automaticamente y el segundo se rellene en función de lo que se pulsa en el primero. Pongo un ejemplo:
1º combo: Provincias españolas(Asturias, Madrid, Barcelona...etc)
2º combo: Cuando se pulse Asturias debera rellenarse con las localidades de Asturias que haya en la base de datos(Gijón, Oviedo, Aviles, Mieres...etc)

Hasta ahora los estaba rellenando con codigo mediante Arrays y funciones, pero el problema de esto es que cada vez que aparezca una nueva localidad en la base de datos(información que no rellenare yo) tendré que entrar en el codigo y meter estas nuevas localidades en los Arrays oportunos.

Tambien probe a rellenarlos mediante GET y POST haciendo consultas a la base de datos y tambien funciona pero queda poco estetico porque me recarga toda la pagina.

Y como me han dicho que con Ajax se puede hacer esto facilmente es por lo que os pido si me podeis decir como se haria paso por paso.

Un saludo.