Erwägungen:
1. 1.1 Der vermutlich aus Russland oder Weissrussland stammende X._ (geb. 1972) stellte in der Schweiz insgesamt drei Asylgesuche. Auf das erste Gesuch trat das Bundesamt für Migration wegen Täuschung über die Identität gemäss Art. 32 Abs. 2 lit. b AsylG (SR 142.31) nicht ein, das zweite Gesuch schrieb es ab und auf das dritte Gesuch trat es mit Entscheid vom 6. November 2008 gestützt auf Art. 32 Abs. 2 lit. e AsylG auch nicht ein und wies X._ aus der Schweiz weg. Den letztgenannten Entscheid bestätigte das Bundesverwaltungsgericht auf Beschwerde hin am 18. November 2008. Von April 2008 bis zum 20. Februar 2009 verbüsste X._ mehrere Gefängnisstrafen wegen diverser Delikte.
1.2 Am 26. Februar 2009 ordnete das Migrationsamt des Kantons Thurgau gegen X._ die Ausschaffungshaft für zunächst drei Monate an, welche das Verwaltungsgericht des Kantons Thurgau am 27. Februar 2009 bewilligte. Dieses hat die Haft am 15. Mai 2009 auf Antrag des kantonalen Migrationsamts um sechs Monate bis zum 26. November 2009 verlängert. Hiegegen gelangt X._ mit Beschwerde vom 9. Juni 2009 an das Bundesgericht. Das kantonale Migrationsamt, das Verwaltungsgericht sowie sinngemäss auch das Bundesamt für Migration stellen den Antrag, die Beschwerde abzuweisen. Die vom kantonalen Migrationsamt und vom Bundesamt erstmals vor Bundesgericht vorgebrachten Noven - zum Erhalt von Ersatz-Reisepapieren durch die Behörden von Weissrussland - können im bundesgerichtlichen Verfahren nicht berücksichtigt werden (vgl. Art. 105 BGG; <ref-ruling> E. 5.1.3 S. 103; <ref-ruling> E. 2.1 S. 344). X._ hat sich innert der angesetzten Frist und bis zum Ergehen des vorliegenden Urteils nicht mehr vernehmen lassen.
2. Fraglich ist bereits, ob die rechtzeitig eingereichte Beschwerde den formellen Anforderungen genügt und damit auf das Rechtsmittel eingetreten werden kann, nachdem der Beschwerdeführer keinen ausdrücklichen Antrag stellt und ein solcher allenfalls aus dem Sinnzusammenhang seiner Eingabe ermittelt werden kann (vgl. Art. 42 Abs. 1 BGG). Mit Blick auf nachfolgende Ausführungen kann diese Frage hier offen gelassen werden.
3. Der Beschwerdeführer macht vorab geltend, die nach Art. 76 Abs. 3 AuG (SR 142.20) insgesamt höchst zulässige Haftdauer werde überschritten. Insoweit unterliegt er jedoch in zweifacher Hinsicht einem Irrtum. Zum einen beträgt die zulässige Höchstdauer für Ausschaffungshaft bei Erwachsenen nicht 15, sondern 18 Monate. Zum anderen handelte es sich bei den vom Beschwerdeführer genannten Gefängnisaufenthalten in 2007 und 2008 um den Vollzug von gegen ihn verhängten Strafen und nicht um Ausschaffungshaft. Diese Zeiten werden nicht in die Berechnung nach Art. 76 Abs. 3 AuG einbezogen.
4. Der Beschwerdeführer bezweifelt des Weiteren das Vorliegen eines Haftgrundes bzw. die Verhältnismässigkeit der Haft. Ihm sei nach der Entlassung aus dem Strafvollzug weder eine Ausreisefrist angesetzt noch ausreichend Zeit zum Verlassen des Landes gewährt worden. Zwecks Ausreise habe er unverzüglich zwei Botschaften aufgesucht. Dort sei er von der Polizei festgenommen und anschliessend in die Ausschaffungshaft überführt worden.
4.1 Die Vorinstanzen haben als Haftgründe nach Art. 76 Abs. 1 lit. b Ziff. 3 und 4 AuG Untertauchensgefahr bzw. die Verletzung der Mitwirkungspflicht angeführt. Gemäss Art. 90 AuG trifft den Ausländer eine Mitwirkungspflicht. Unter anderem muss er zutreffende und vollständige Angaben zu seiner Person machen und gültige Ausweispapiere beschaffen bzw. bei deren Beschaffung durch die Behörden mitwirken.
Der Beschwerdeführer versuchte, in mehreren Ländern Europas unter verschiedenen Identitäten einen Aufenthaltsstatus zu erlangen. Ein gültiges Ausweispapier hat er in der Schweiz nicht vorgelegt. Bei Anordnung der Ausschaffungshaft stand seine Identität und Herkunft nicht fest. Ein Gespräch mit einem Länderexperten brachte der Beschwerdeführer zum Scheitern. Demzufolge sind die erwähnten Haftgründe ohne Weiteres erfüllt. Daran ändert nichts, dass der Beschwerdeführer möglicherweise bei der Botschaft der USA, vor der er nach Büroschluss in angetrunkenem Zustand ergriffen wurde, vorsprechen wollte. Auch dort konnte er keine gültigen Ausweispapiere vorweisen; zudem gibt es keine Hinweise darauf, dass er Bürger dieses Staates ist; das behauptet der Beschwerdeführer auch nicht.
Ob der von der Vorinstanz zusätzlich angeführte Haftgrund des Art. 76 Abs. 1 lit. b Ziff. 2 AuG gegeben ist, nachdem sich der Beschwerdeführer nach Ergehen des Nichteintretensentscheides im Asylverfahren gemäss Art. 32 Abs. 2 lit. b AsylG einstweilen im Ausland aufgehalten und nach Rückkehr in die Schweiz ein neues Asylgesuch gestellt hatte, kann offen gelassen werden.
4.2 Wie die Vorinstanz in ihrem ersten Entscheid vom 27. Februar 2009 zutreffend bemerkt hat, hätte der Beschwerdeführer - mit Blick auf obige Ausführungen - nach dem Strafvollzug sofort in die Ausschaffungshaft überführt werden können. Die Behörden mussten ihm demnach nicht zunächst eine Ausreisefrist ansetzen bzw. Zeit lassen, um nach der Strafhaft Reisepapiere zu besorgen und freiwillig auszureisen. Wollen die Behörden den Ausländer nach Verbüssung einer Gefängnisstrafe aber unmittelbar in Ausschaffungshaft nehmen, so sind sie verpflichtet, bei klarer fremdenpolizeilicher Ausgangslage bereits während des Strafvollzugs Vorbereitungen für die Ausschaffung einzuleiten (vgl. Beschleunigungsgebot gemäss Art. 76 Abs. 4 AuG); diese Pflicht beginnt nicht erst mit der Anordnung der Ausschaffungshaft (<ref-ruling> E. 3a S. 50 mit Hinweisen). Nachdem auch das dritte Asylgesuch des Beschwerdeführers im November 2008 erfolglos geblieben war, ersuchten die kantonalen Behörden das Bundesamt für Migration noch im selben Monat um Vollzugsunterstützung. Kurz nach Beginn der Ausschaffungshaft sollte das erwähnte Gespräch mit dem Länderexperten stattfinden. Wie aus den Akten zu entnehmen ist, blieben die Behörden auch in der Folge nicht untätig, um die Identität des Beschwerdeführers zu ermitteln und Reisepapiere zu besorgen, weshalb das Beschleunigungsgebot als gewahrt gelten kann.
Wohl haben die Vorinstanzen die Haft nicht wie üblich um zunächst drei Monate, sondern sogleich um sechs Monate verlängert. Wegen der bis dahin - trotz diverser Abklärungen - ungewissen Identität und Herkunft des Beschwerdeführers gekoppelt mit seinem renitenten Verhalten erscheint diese Verlängerung noch als vertretbar (vgl. <ref-ruling> E. 4 S. 440 ff.). Im Übrigen wird der Beschwerdeführer Haftentlassungsgesuche gemäss Art. 80 Abs. 5 AuG nach einem bzw. zwei Monaten stellen können, bei denen der Haftrichter ein besonderes Augenmerk auf die weitere Beachtung des Beschleunigungsgebots wird richten müssen.
5. Nach dem Dargelegten erweist sich die Ausschaffungshaft als verhältnismässig. Die offensichtlich unbegründete Beschwerde ist daher im vereinfachten Verfahren nach Art. 109 BGG abzuweisen, soweit auf sie einzutreten ist.
Bei diesem Ausgang hätte der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen. Mit Blick auf seine Situation wird jedoch praxisgemäss auf die Erhebung von Gerichtskosten verzichtet (Art. 65 f. BGG).
Das Migrationsamt des Kantons Thurgau wird dazu angehalten, dafür besorgt zu sein, dass dem Beschwerdeführer der vorliegende Entscheid korrekt eröffnet und verständlich gemacht wird.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Es werden keine Gerichtskosten erhoben.
3. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt und Verwaltungsgericht des Kantons Thurgau sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 8. Juli 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Merz