Sachverhalt:
A. A.a Am 15. Juni 1992 überkletterten A._ und B._ den Grenzzaun, um von Konstanz (Deutschland) nach Kreuzlingen zu gelangen. Sie führten sechs Kilogramm Heroin mit sich. Die schweizerische Grenzwache nahm die beiden fest. Im Laufe des Ermittlungsverfahrens stellte sich heraus, dass die Verhafteten nach der Einreise X._ und C._ im Restaurant D._ treffen wollten, um mit deren Hilfe die Drogen nach Rorschach weiterzutransportieren und an Dritte zu übergeben.
A.b Die Staatsanwaltschaft des Kantons Thurgau klagte X._ am 29. März 1993 wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz an und beantragte eine Zuchthausstrafe von vier Jahren.
A.c Das Bezirksgericht Kreuzlingen lud X._ am 26. April 1993 zur Hauptverhandlung vom 21. Juni 1993 vor. Wenige Tage später ersuchte der amtliche Verteidiger um freies Geleit für X._. Das Bezirksgericht Kreuzlingen bewilligte dieses Gesuch am 6. Mai 1993. X._ reiste am 7. Mai 1993 aus der Schweiz aus, nachdem sein Asylgesuch definitiv abgelehnt worden war. Er blieb der Hauptverhandlung vom 21. Juni 1993 fern.
A.d Das Bezirksgericht Kreuzlingen verurteilte X._ am 21. Juni 1993 im Abwesenheitsverfahren wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz zu fünf Jahren Zuchthaus, unter Anrechnung der Untersuchungshaft von 70 Tagen. Dieses Urteil erwuchs unangefochten in Rechtskraft.
A.e Am 10. Oktober 2011 wurde X._ bei seiner Einreise in die Schweiz verhaftet und dem Strafvollzug zugeführt.
B. X._ beantragte am 19. Oktober 2011, das Strafverfahren sei neu zu beurteilen, und es sei festzustellen, dass die Verfolgungsverjährung eingetreten sei. Die Berufungsfrist sei wiederherzustellen. Das Bezirksgericht Kreuzlingen wies das Gesuch mit Beschluss vom 30. Dezember 2011 ab. Das Obergericht des Kantons Thurgau lehnte die dagegen gerichtete Beschwerde am 9. Februar 2012 ab, soweit auf sie einzutreten war.
C. X._ erhebt gegen das Urteil des Obergerichts Beschwerde in Strafsachen. Er beantragt, das angefochtene Urteil sei aufzuheben. Das Bezirksgericht Kreuzlingen sei anzuweisen, das Urteil vom 21. Juni 1993 aufzuheben, das Verfahren wieder aufzunehmen, die Verjährung zu prüfen und festzustellen, dass diese eingetreten sei. Eventualiter sei die Frist zur Anmeldung der Berufung gegen das Urteil des Bezirksgerichts Kreuzlingen vom 21. Juni 1993 wiederherzustellen, und es sei festzustellen, dass diese gewahrt worden sei, unter Kosten- und Entschädigungsfolgen zulasten der Vorinstanz. Es sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu bewilligen.
D. Das Gesuch von X._ um aufschiebende Wirkung bzw. um Haftentlassung wurde mit Präsidialverfügung vom 17. April 2012 abgewiesen.
E. Das Obergericht und die Staatsanwaltschaft beantragen die Abweisung der Beschwerde.
F. Das Bundesgericht hat den Entscheid öffentlich beraten.
Erwägungen:
1. Nicht einzutreten ist auf die Ausführungen, in welchen der Beschwerdeführer auf frühere Rechtsschriften verweist (vgl. Beschwerde S. 8 und S. 10; BGE 133 II 396 E. 3.1 mit Hinweisen).
2. 2.1 Der Beschwerdeführer rügt, der von der Vorinstanz hinsichtlich des Gesuchs um Neubeurteilung festgestellte Sachverhalt sei willkürlich. Aus seinem Antrag um freies Geleit könne nicht abgeleitet werden, er habe Kenntnis von der Vorladung gehabt. Der Kontakt zu seinem Verteidiger sei abgebrochen gewesen. Dieser habe seine Interessen ohne Rücksprache bestmöglich wahren wollen.
2.2 Die Sachverhaltsfeststellung der Vorinstanz kann nur gerügt werden, wenn sie willkürlich (Art. 9 BV) ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG; BGE 134 IV 36 E. 1.4.1). Willkür bei der Beweiswürdigung liegt vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist oder mit der tatsächlichen Situation in klarem Widerspruch steht. Dass eine andere Lösung oder Würdigung ebenfalls vertretbar oder gar zutreffender erscheint, genügt für die Annahme von Willkür nicht (BGE 137 I 1 E. 2.4; 134 I 140 E. 5.4; je mit Hinweisen).
2.3 Die Vorinstanz erwägt, der Beschwerdeführer habe von der Vorladung und der Anklageschrift gewusst. Dies ergebe sich aus seinem Antrag vom 29. April 1993 auf freies Geleit (Urteil S. 8, S. 10). Darin führt der Rechtsvertreter des Beschwerdeführers wörtlich aus:
"In oberwähnter Strafsache findet am 21.06.1993, 08.00 Uhr, die Gerichtsverhandlung statt. Da die Schweizerische Asylrekurskommission das Asylgesuch des Angeklagten am 02.04.1993 rechtskräftig abgewiesen hat und er demzufolge die Schweiz bis zum 15.05.1993 verlassen muss, kann er an der Gerichtsverhandlung nicht teilnehmen. X._ möchte jedoch unbedingt an der Gerichtsverhandlung selbst auch teilnehmen, weshalb ich Sie ersuche, ihm freies Geleit zuzusichern, und zwar in der Weise, als er wegen der in der 'Geleitserklärung' bezeichneten strafbaren Handlung nicht in Haft gesetzt wird."
2.4 Die Vorinstanz durfte ohne Willkür zum Schluss gelangen, der Beschwerdeführer habe die Anklage und die Vorladung zur Hauptverhandlung erhalten und darüber mit seinem amtlichen Verteidiger gesprochen. Dieser konnte Ende April 1993 nur aufgrund einer aktuellen Instruktion durch den Beschwerdeführer wissen, dass dessen Asylgesuch Anfang April 1993 definitiv abgewiesen worden war. Ein vorsorglich, ohne Absprache mit dem Beschwerdeführer erfolgter Antrag um freies Geleit fällt aufgrund der Wortwahl des Verteidigers, sein Mandant wolle als Angeklagter "unbedingt" an der Verhandlung vom 21. Juni 1993 teilnehmen, ausser Betracht. Nur der Beschwerdeführer konnte entscheiden, ob er den Aufwand einer Wiedereinreise auf sich nehmen wollte. Das Argument, der Kontakt zum Verteidiger sei abgebrochen gewesen, ist daher nicht stichhaltig. Hinzu kommt, dass sich auch den Akten, namentlich dem Urteil vom 21. Juni 1993, keine Hinweise entnehmen lassen, dass der Beschwerdeführer vor der Hauptverhandlung keinen Kontakt mehr zu seinem damaligen Verteidiger hatte. Für den Erhalt der Vorladung spricht schliesslich der Umstand, dass die Vorladung an die vom Beschwerdeführer wiederholt angegebene Zustelladresse erfolgte, und die Post die eingeschriebene Sendung nicht als unzustellbar an das Gericht zurücksandte (Urteil S. 7 mit Verweis auf das erstinstanzliche Urteil S. 14). Hingegen lässt sich aus den aktuelleren Visumsanträgen und aus der Einreise kurz vor Ablauf der Vollzugsverjährung (Beschwerde S. 7, S. 10, S. 12) nichts zum Informationsstand des Beschwerdeführers im früheren Verfahren ableiten. Die Rügen erweisen sich als unbegründet, soweit darauf einzutreten ist (Art. 97 Abs. 1 und Art. 106 Abs. 2 BGG; BGE 136 I 65 E. 1.3.1 mit Hinweisen).
3. 3.1 Der Beschwerdeführer beanstandet, die Vorinstanz lehne seinen Antrag auf eine neue Beurteilung des Strafverfahrens zu Unrecht ab. Die Vorinstanz verletze Art. 368 StPO (SR 321.0), die Ansprüche auf rechtliches Gehör nach Art. 29 Abs. 1 und Abs. 2 BV und auf ein faires Verfahren nach Art. 6 Ziff. 2 EMRK sowie das Willkürverbot nach Art. 9 BV.
3.2 Gemäss der übergangsrechtlichen Bestimmung von Art. 452 Abs. 2 StPO werden nach dem 1. Januar 2011 gestellte Gesuche um neue Beurteilung nach einem unter dem kantonalen Strafprozessrecht ergangenen Abwesenheitsurteil nach dem Recht beurteilt, das für die gesuchstellende Person günstiger ist. Der Beschwerdeführer geht mit der Vorinstanz von der Anwendbarkeit von Art. 368 StPO als günstigerem Recht aus.
3.2 Gemäss der übergangsrechtlichen Bestimmung von Art. 452 Abs. 2 StPO werden nach dem 1. Januar 2011 gestellte Gesuche um neue Beurteilung nach einem unter dem kantonalen Strafprozessrecht ergangenen Abwesenheitsurteil nach dem Recht beurteilt, das für die gesuchstellende Person günstiger ist. Der Beschwerdeführer geht mit der Vorinstanz von der Anwendbarkeit von Art. 368 StPO als günstigerem Recht aus.
3.3 3.3.1 Das Recht auf persönliche Teilnahme an der Verhandlung ergibt sich aus den Ansprüchen auf rechtliches Gehör nach Art. 29 Abs. 2 BV und auf ein faires Verfahren nach Art. 6 Ziff. 1 EMRK. Es gilt jedoch nicht absolut. Abwesenheitsverfahren sind zulässig, sofern der Verurteilte nachträglich verlangen kann, dass ein Gericht, nachdem es ihn zur Sache angehört hat, nochmals überprüft, ob die gegen ihn erhobenen Beschuldigungen begründet sind. Der Anspruch auf Neubeurteilung kann von bestimmten Formen und Fristen abhängig gemacht werden. Ferner ist es mit Art. 29 Abs. 2 BV und Art. 6 Ziff. 1 EMRK vereinbar, wenn eine Neubeurteilung deswegen abgelehnt wird, weil der in Abwesenheit Verurteilte sich geweigert hat, an der Verhandlung teilzunehmen oder er die Unmöglichkeit, dies zu tun, selbst verschuldet hat (BGE 129 II 56 E. 6.2 mit Hinweisen, namentlich auf die Rechtsprechung des EGMR). Nach der bundesgerichtlichen Praxis ist die Abwesenheit nicht nur im Falle höherer Gewalt, d.h. bei objektiver Unmöglichkeit zu erscheinen, gültig entschuldigt, sondern auch im Falle subjektiver Unmöglichkeit aufgrund der persönlichen Umstände oder eines Irrtums (BGE 127 I 213 E. 3a; 126 I 36 E. 1b). Abwesenheit aus Furcht vor einer Verhaftung wird gemäss BGE 127 I 213 E. 4 nicht als entschuldbare subjektive Unmöglichkeit gewertet, da das öffentliche Interesse an der Durchführung des Strafverfahrens (auch gegen einen Abwesenden) schwerer wiegt als das gegenläufige persönliche Interesse des Beschuldigten, sich einer in einem anderen Verfahren bereits rechtskräftig ausgesprochenen Strafe durch Flucht entziehen zu können. Hingegen ist die Wiederaufnahme des Strafverfahrens grundsätzlich zu gewährleisten, wenn der in Abwesenheit Verurteilte von der gerichtlichen Vorladung keine Kenntnis erhalten und auch nicht versucht hat, sich der Strafverfolgung zu entziehen (BGE 129 II 56 E. 6.2 mit Hinweisen).
3.3.2 Diese Rechtsprechung wurde in Art. 368 StPO verankert. Gemäss Art. 368 Abs. 3 StPO lehnt das Gericht das Gesuch um Neubeurteilung ab, wenn die verurteilte Person ordnungsgemäss vorgeladen worden, aber der Hauptverhandlung unentschuldigt ferngeblieben ist.
In Anlehnung an die Rechtsprechung des EGMR dürfen an die Entschuldbarkeit des Fernbleibens im Sinne von Art. 368 Abs. 3 StPO keine strengen Anforderungen gestellt werden. Verlangt wird, dass die beschuldigte Person der Verhandlung bewusst und freiwillig fernblieb (vgl. etwa NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2009, N. 5 zu Art. 368 StPO; DERS., Handbuch des schweizerischen Strafprozessrechts, 2009, N. 1411 S. 645; SARAH SUMMERS, in: Kommentar zur Schweizerischen Strafprozessordnung, Donatsch/Hansjakob/Lieber [Hrsg.], 2010, N. 8 zu Art. 368 StPO; vgl. auch THOMAS MAURER, in: Schweizerische Strafprozessordnung, Basler Kommentar, N. 15 zu Art. 368 StPO; GOLDSCHMID/MAURER/SOLLBERGER, Kommentierte Textausgabe zur Schweizerischen Strafprozessordnung, 2008, zu Art. 368 StPO). Der Betroffene muss die entschuldigenden Gründe glaubhaft vorbringen. Der Nachweis, dass die Abwesenheit verschuldet war, obliegt dem Staat (vgl. BGE 129 II 56 E. 6.2; SCHMID, Praxiskommentar, a.a.O., N. 6 zu Art. 368 StPO; DERS., Handbuch, a.a.O., N. 1411 S. 645; SUMMERS, a.a.O., N. 13 f. zu Art. 368 StPO; MAURER, a.a.O., N. 15 zu Art. 368 StPO).
3.4 Die Vorinstanz durfte eine ordnungsgemässe Vorladung gemäss Art. 368 Abs. 3 StPO bejahen. Der Beschwerdeführer hatte nach den willkürfreien Feststellungen der Vorinstanz Kenntnis vom Verhandlungstermin und von der Anklage (vgl. oben E. 2). Seine Einwände gegen die gesetzeskonforme Zustellung sind nicht stichhaltig.
3.5 Der Beschwerdeführer verkennt, dass die Landesabwesenheit für sich gesehen keine Entschuldbarkeit im Sinne von Art. 368 Abs. 3 StPO begründet. Mit der Bewilligung des freien Geleits schuf das Bezirksgericht Kreuzlingen die Möglichkeit, dass der Beschwerdeführer nach seiner migrationsrechtlichen Wegweisung zur Verhandlung vom 21. Juni 1993 in die Schweiz einreisen konnte. Weitere Gründe, welche die Abwesenheit als unverschuldet erscheinen lassen könnten, macht er nach zutreffender Auffassung der Vorinstanz nicht glaubhaft. Insbesondere behauptet er nicht, er habe aus finanziellen Gründen auf die Reise verzichtet oder die türkischen Behörden hätten ihn zur Zeit der Verhandlung festgehalten. Die angeblichen Verhöre durch die türkischen Behörden bei der Einreise in sein Heimatland sowie die Organisation von Unterkunft und Arbeit reichen nicht aus, um die Abwesenheit an der Verhandlung zu entschuldigen, weil diese Termine zeitlich koordiniert werden konnten. Soweit der Beschwerdeführer die Aufmerksamkeit der türkischen Behörden durch eine erneute Ausreise nicht auf sich bzw. auf seine Familie lenken wollte (Beschwerde S. 10 f.), begründet dies keinen entschuldbaren Hinderungsgrund. Der Beschwerdeführer konnte auch nicht annehmen, das Verfahren habe sich erledigt. Ihm stand ein amtlicher Verteidiger zur Seite, der ihn zum Verfahrensablauf beraten und den er jederzeit kontaktieren konnte. Aufgrund der längeren Untersuchungshaft und des hohen Strafantrags der Staatsanwaltschaft lag es auf der Hand, dass das Strafverfahren schwerwiegende Vorwürfe umfasste, die nicht formlos fallen gelassen würden. Der Beschwerdeführer kann sich nicht darauf berufen, er sei stets von seiner Unschuld bzw. von harmlosen Vorwürfen ausgegangen, und die Mitangeklagten hätten ihn erst in der Hauptverhandlung erheblich belastet (vgl. Beschwerde S. 9). Seine Rügen sind unbegründet.
4. 4.1 Der Beschwerdeführer macht geltend, die Vorinstanz verletze Art. 94 StPO, indem sie die Wiederherstellung der Berufungsfrist ablehne.
4.2 Die Vorinstanz geht davon aus, das Urteil vom 21. Juni 1993 sei dem Beschwerdeführer gültig zugestellt worden (Urteil S. 10). Der Beschwerdeführer beanstandet dies nicht.
4.3 Für die Frage, ob der Beschwerdeführer Anspruch auf Wiederherstellung der Berufungsfrist hat, muss das bis am 31. Dezember 2010 geltende kantonale Strafprozessrecht zur Anwendung gelangen, wenn das erstinstanzliche Urteil wie vorliegend vor dem 1. Januar 2011 erging und sich gemäss Art. 453 Abs. 1 StPO auch das Berufungsverfahren nach dem alten Prozessrecht richtet (vgl. NIKLAUS SCHMID, Übergangsrecht der Schweizerischen Strafprozessordnung, 2010, N. 112 f. S. 31).
Nachdem die Vorinstanz zu Unrecht von der Anwendbarkeit der StPO ausgeht, kann dem Beschwerdeführer nicht zum Vorwurf gemacht werden, dass er sich in seiner Beschwerde auf Art. 94 StPO beruft und keine willkürliche Anwendung der thurgauischen Strafprozessordnung rügt. Da sowohl Art. 94 Abs. 1 StPO als auch § 43 Abs. 2 StPO/TG vom Beschwerdeführer verlangen, dass er zumindest glaubhaft macht, dass ihn an der Säumnis kein Verschulden trifft, schadet ihm die Anwendung des neuen anstelle des alten Prozessrechts aber nicht.
4.4 In der Sache durfte die Vorinstanz eine unverschuldete Säumnis verneinen. Der Beschwerdeführer wiederholt, er sei erst an der Hauptverhandlung von den Mitangeklagten massiv belastet worden, er habe keinen Kontakt zu seinem amtlichen Verteidiger gehabt, dieser habe seine Interessen mangels Anfechtung des Urteils nicht hinreichend wahrgenommen oder er sei ein Jahr vor Ablauf der Vollzugsverjährung in die Schweiz eingereist, was die fehlende Kenntnis von der Verurteilung belege (Beschwerde S. 10 ff.).
Diese Rügen sind nicht geeignet, das fehlende Verschulden an der Säumnis glaubhaft darzutun. Der von Beschwerdeführer zu verantwortende spätere Abbruch des Kontakts zu seinem Verteidiger in der Schweiz lässt die Säumnis nicht entschuldbar erscheinen. Entgegen dem Einwand des Beschwerdeführers kann dem amtlichen Verteidiger nicht zum Vorwurf gemacht werden, dass er den Entscheid vom 21. Juni 1993 nicht vorsorglich anfocht, da nicht gegen jedes erstinstanzliche Urteil der Rechtsmittelweg ergriffen werden muss und sich der Beschwerdeführer - wie sich gezeigt hat - bis zu seiner Festnahme im Jahre 2011 auch nicht weiter um das Urteil kümmern wollte.
5. 5.1 Der Beschwerdeführer wendet ein, das öffentliche Interesse und das Verhältnismässigkeitsprinzip nach Art. 5 Abs. 2 BV bzw. § 2 Abs. 2 und § 8 Abs. 1 der Verfassung des Kantons Thurgau vom 16. März 1987 (KV/TG; RB 101) seien verletzt, sofern die Strafe vollzogen werde. Infolge des Zeitablaufs habe das Strafbedürfnis abgenommen. Er habe sich nichts mehr zuschulden kommen lassen.
5.2 Der Gesetzgeber hat mit den Bestimmungen über die Vollstreckungsverjährung geregelt, wie lange der Vollzug einer Strafe im öffentlichen Interesse liegt und verhältnismässig ist. Er ging davon aus, bis zu den in Art. 99 Abs. 1 StGB festgesetzten Fristen seien ein öffentliches Interesse am Strafvollzug gegeben und der Verhältnismässigkeitsgrundsatz gewahrt. Das Bundesgericht ist daran gebunden (Art. 190 BV). Eine Verletzung von Art. 99 Abs. 1 StGB macht der Beschwerdeführer zu Recht nicht geltend.
6. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist gutzuheissen, da die Beschwerde nicht von vornherein aussichtslos war und die Bedürftigkeit des Beschwerdeführers erstellt scheint (Art. 64 Abs. 1 und 2 BGG). Es sind keine Kosten zu erheben. Der Vertreter des Beschwerdeführers ist für das Verfahren vor dem Bundesgericht aus der Bundesgerichtskasse zu entschädigen.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3. Es werden keine Kosten erhoben.
4. Dem Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Bernhard Jüsi, wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Thurgau schriftlich mitgeteilt.
Lausanne, 30. August 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Unseld