bueno en tu html donde tenes las letras
cada letra tiene q ser un link a una pagina tipo: "ciudades.php?letra=a"
en ciudades.php
-Te conectas a la DB
-Ejecutar la consulta tipo: "SELECT * FROM ciudades WHERE nombre LIKE '$letra%'"
donde $letra = $_GET['letra']
para saber como ejecutar una consulta:
mysql_query
para saber como mostrar resultados de una consulta
mysql_fetch_assoc