yo haría lo mismo que manoloweb, pero si quieres contar las distintas localicades de cada provincia(en el caso de que tengas también el campo provincia) añádele un group by:
SELECT COUNT(DISTINCT localidad)
FROM tutabla
GROUP BY provincia
si tienes 5 provincias, te saldrán 5 números, una por cantidad de distintas localidades por provincia.
suerte.
