Código PHP:
$letra_anterior = "";
while($row = mysql_fetch_array($id_result)) {
$letra_actual = substr($row['campo'], 0, 1); // Metemos en una variable la primera letra de la palabra.
if (!strcasecmp($letra_anterior,$letra_actual)) { // comparamos ambas letras
$letra anterior = $letra_actual;
echo "$letra_actual <br/>";
}
echo "$row['campo'] <br/>";
}
$id_result es el resultado de la consulta a la BDD
campo es el campo de la tabla donde están las palabras.
No he comprobado que funcione, pero tienes por donde empezar.