Si quieres usar PHP sólo y tus paises/provincias o estados están en una BD .. podrías usar este ejemplo:
http://www.forosdelweb.com/f18/faqs-php-530600-post664999/
También puedes hacerlo integramente con Javascript (si los datos son fijos) o con hibridos entre PHP y Javascript.
Un saludo,