Ich muss aus einer Datenbank Koordinaten von Haltestellen holen. Das Problem sind die Namen der Haltestellen. So beziehen sich "Berlin Hauptbahnhof", "Berlin Hbf", "Hbf Berlin",... alle auf die selbe Haltestelle, und verschiedene Systeme benutzen verschidenen dieser Namen.

Das Problem könnte man doch am einfachsten mit einem String-Ähnlichkeits-Vergleich lösen. Alson einfach die zu 5 ähnlichsten Strings zu "Berlin Hauptbahnhof" auswählen, und die mit der geringsten Entferung zur Position des Nutzers wählen.

Welchen Algorithmus zur Berechnung der Ähnlichkeit der Strings könnte ich nehmen?

In Deinem Fall ist es mit einem Ähnlichkeits-Vergleich leider nicht getan, da ja auch Abkürzungen erkannt werden sollen.
Es gibt für MySQL die Möglichkeit SOUNDEX zu verwenden, aber das liefert nicht soo dolle Ergebnisse.
Aus der MySQL Doku:

mysql> SELECT SOUNDEX('Hello');
        -> 'H400'
mysql> SELECT SOUNDEX('Quadratically');
        -> 'Q36324'

Wenn Du von SQL absiehst, dann müsstest Du die Ergebnisse nachfiltern. Da gibt es verschiedene Algorithmen. Vielleicht klappt bei Dir ja das mit dern Levenshtein-Distanz.
Du solltest aber auf jeden Fall darüber nachdenken, den Suchalgorithmus 'lernfähig' zu machen, damit er mit der Zeit erkennt, dass 'Hbf' == 'Hauptbahnhof' ist.
Dazu auch noch ein Link: Duplikaterkennung

Folgender Vorschlag:

text1 = 'Berlin Hbf'
text2 = 'Berlin Hautbahnhof'
Wenn GleichheitSchonmalBestätigt(text1,text2) dann Fertig()

token1 = Token aus text1
token2 = Token aus text2
fast = 0
Für alle t1 in token 1
  Für alle t2 in token2
    Wenn IstAehnlich(t1,t2) dann fast = 1

Wenn fast = 1 dann 
  Wenn FrageUserObGleich(text1,text2) dann MerkeDassGleich(text1,text2)

Mein Lieblingsähnlichkeitsalgorithmus ist die Trigramm-Methode. Sie ist für ein Trigramm-Perlmodul hier beschrieben. Ob es entsprechende Libraries für Java gibt, weiß ich nicht, das ganze wäre aber auch nicht besonders schwer zu programmieren.

Wenn du deine Datenbasis über Lucene zugänglich machst, bekommst du eine Fuzzysuche schon mitgeliefert. Die basiert glaube ich auf Levenshtein, da Lucene aber gut erweiterbar ist, könnte man auch andere Algorithmen implementieren.

Welchen Algorithmus man auch immer nimmt, eine vorherige Normalisierung empfiehlt sich auf jeden Fall (alles in Kleinbuchstaben umwandeln, Umlaute etc. normalisieren, evtl. Leerzeichen entfernen, ...).

Wie bereits von DaSpors erwähnt wäre die Levenshtein-Distanz eine Lösung. Dies kann dann als Fuzzy-Suche implementiert werden. Eine Implementierung dessen in C# gibt hier.

Ein komplett anderer Ansatz der mir einfällt wäre einen Assoziativspeicher mittels neuronalem Netz zu erstellen. Habs nicht probiert kann mir aber gut vorstellen dass das geht - ähnlich wie Kohonen's WebSOM.
Dadurch sollte es bei korrekter Implementierung auch möglich sein Berlin Hbf und Hbf Berlin dem selben Ausgangsmerkmal zuzuordnen.

Wenn die Anzahl der eingabefähigen Haltestellen bekannt ist und auch die Strings die tatsächlich verwendet werden, ist es vielleicht performanter eine Thesaurus-Tabelle in der Datenbank zu basteln, deinen Eingabestring auf lowercase und ohne leer- und sonderzeichen zu formatieren und das mit einem SQL-Statement abzufackeln. Der Thesaurus mappt dann auf die korrekte Bezeichnung.

Der Aufwand besteht dann aber in der Thesauruspflege. GGf. hat deine Datenbank aber schon eine Thesaurierungsfunktion dabei. Dann eben diese.

Würde ich aber nur machen, wenn ich keine freien Benutzereingaben verarbeiten muss, sondern quasi statische Strings.