Sachverhalt:
A. A.a A._ (Kläger, Beschwerdeführer) ist bulgarischer Staatsbürger und wohnt in Sofia. Er war Cheftrainer der nationalen Fussballmannschaft Bulgariens.
Die Bulgarische Fussballunion (BFU, Beklagte, Beschwerdegegnerin) ist der nationale Fussballverband Bulgariens. Sie gehört der Fédération Internationale de Football Association (FIFA) an.
A.b Am 11. Januar 2008 schlossen die Parteien einen Arbeitsvertrag ab, mit dem der Kläger für eine feste Zeitdauer bis zum 31. Dezember 2009 als Cheftrainer der bulgarischen Nationalmannschaft eingestellt wurde gegen einen Monatslohn von EUR 11'000.--, zuzüglich erfolgsabhängige Boni und Spesen.
Ziffer 16 des Arbeitsvertrags lautet wie folgt:
"The disputes concerning the interpretation of the meaning and the performance of the contract will be resolved amicably by agreement of the parties. In case an agreement is impossible to reach, the dispute shall be referred for resolving by the competent court. The parties to the contract recognize the Court of Arbitration for Sport (CAS) in Lausanne, Switzerland as in this case the Statute and the regulations of BFU and the provisions of Bulgarian legislation will apply."
Am 13. Januar 2009 kündigte die Beklagte das Arbeitsverhältnis vorzeitig und zahlte dem Kläger einen Monatslohn aus.
A.c Am 19. Januar 2009 leitete der Kläger beim Regionalgericht Sofia ein Zivilverfahren ein und beantragte, die Beklagte sei zur Zahlung von EUR 132'000.-- zu verurteilen. Das Regionalgericht erklärte sich mit der Begründung für zuständig, arbeitsrechtliche Streitigkeiten seien nach Art. 19 Abs. 1 der bulgarischen Zivilprozessordnung (bZPO) nicht schiedsfähig, sondern müssten von den staatlichen Gerichten beurteilt werden. Das Gericht wies die Klage jedoch ab, indem es erwog, die vom Kläger angerufene Vertragsbestimmung, nach der bei einseitiger Vertragsauflösung eine Konventionalstrafe geschuldet ist, widerspreche dem bulgarischen Arbeitsrecht und sei nichtig.
Art. 19 Abs. 1 bZPO sieht (in seiner englischen Übersetzung) Folgendes vor:
"The parties to a property dispute may agree that it be settled by a court of arbitration, unless the dispute has as its subject property rights or possession of immoveable property, alimony or rights as per employment relationship."
A.d Am 13. Oktober 2011 reichte der Kläger beim Regionalgericht Sofia eine weitere Klage ein und verlangte eine Entschädigung von sechs Monatslöhnen wegen Vertragsverletzung. Das Regionalgericht erklärte sich mangels Schiedsfähigkeit der Streitsache wiederum in Anwendung von Art. 19 bZPO für zuständig. Das Regionalgericht vertagte das Verfahren und lud die Parteien auf den 8. Mai 2012 zu einer Verhandlung.
B. Am 8. November 2011 erhob der Kläger beim Tribunal Arbitral du Sport (TAS) Schiedsklage gegen die Beklagte und stellte im Verfahrensverlauf die folgenden Rechtsbegehren:
"a. Declare that the CAS has jurisdiction over the dispute and the Parties to this arbitration.
b. Declare that the Employment Contract dated 11 January 2008 entered into by and between the Bulgarian Football Union (the Respondent) and Mr. A._ (the Claimant) was terminated without just cause;
c. Order BFU to pay to the Claimant as compensation for the termination of the Employment Contract 11 salaries in the amount of EUR 121,000 corresponding to the remaining value of the Employment Contract;
d. Order BFU to pay to the Claimant simple interest at 5 % per annum on the amount of EUR 121,000 from 15 January 2009 until full and final payment;
e. Order BFU to pay to the Claimant further allowances and payments listed in para. 20 of the RFA [Request for Arbitration] above the amount of which is to be further specified;
f. Order BFU to pay to the Claimant simple interest at 5 % per annum on the amounts related to further allowances and payments listed in para. 20 of the RFA from issuance of the award until full and final payment;
g. Order BFU to pay all the costs of the arbitration, including without limitation the fees and expenses of the Panel and the CAS;
h. Order BFU to pay to the Claimant its legal fees and expenses;
i. Award such other relief as the Panel deems appropriate."
Die Beklagte erhob die Einrede der Unzuständigkeit: Der Rechtsstreit sei nicht schiedsfähig und zwingend von den staatlichen Gerichten in Bulgarien zu beurteilen, die Schiedsvereinbarung sei ungültig und der Kläger habe auf die Anrufung der Schiedsklausel verzichtet. Im Weiteren stehe der erhobenen Schiedsklage die Rechtskraftwirkung bereits ergangener Gerichtsurteile (res iudicata) entgegen.
Mit Schiedsentscheid vom 24. Mai 2012 erklärte sich das TAS mangels Schiedsfähigkeit für unzuständig. Es erachtete Art. 19 Abs. 1 bZPO für anwendbar, der arbeitsrechtliche Streitigkeiten von der Beurteilung durch ein Schiedsgericht ausschliesst. Diesem Ergebnis stehe auch <ref-law> nicht im Weg, zumal das IPRG eine Berücksichtigung zwingender Bestimmungen eines ausländischen Rechts zulasse. Im Weiteren wies das TAS darauf hin, es bestehe die reelle Gefahr, dass ein Schiedsentscheid des TAS in Bulgarien nicht durchgesetzt werden könne.
C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, der Schiedsentscheid vom 24. Mai 2012 sei aufzuheben und das TAS sei für zuständig zu erklären.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Das TAS hat auf eine Vernehmlassung verzichtet.
Der Beschwerdeführer hat dem Bundesgericht am 28. November 2012 eine Replik, die Beschwerdegegnerin am 20. Dezember 2012 eine Duplik eingereicht.

Erwägungen:
1. Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser in einer anderen Sprache redigiert, verwendet das Bundesgericht die von den Parteien gewählte Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht der deutschen Sprache bedienen, ergeht der Entscheid des Bundesgerichts auf Deutsch.
2. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Beide Parteien hatten im relevanten Zeitpunkt ihren Sitz bzw. Wohnsitz ausserhalb der Schweiz. Da die Parteien die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
2.2 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts betrifft, gilt davon allerdings eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen kann (<ref-ruling> E. 3.3.4 S. 616 mit Hinweisen). Der Antrag des Beschwerdeführers ist insofern zulässig.
3. Der Beschwerdeführer macht geltend, das TAS habe sich zu Unrecht für unzuständig erklärt (<ref-law>), da es sich bei seiner Klage entgegen dem angefochtenen Entscheid um eine schiedsfähige Streitsache handle.
3.1 Die Voraussetzung der Schiedsfähigkeit der Streitsache ist im Rahmen der Zuständigkeitsbeschwerde (<ref-law>) zu prüfen (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 3a S. 355). Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt, in rechtlicher Hinsicht frei. Demgegenüber überprüft es die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 2.2.1 S. 34; <ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141).
Wird im Beschwerdeverfahren die Rüge der Unzuständigkeit erhoben und ist diese hinreichend begründet, prüft das Bundesgericht sämtliche rechtlichen Gesichtspunkte frei (iura novit curia), womit es gegebenenfalls veranlasst wird, die erhobene Rüge mit einer anderen Begründung zu verwerfen als die im angefochtenen Schiedsentscheid aufgeführte (Urteil 4A_392/2008 vom 22. Dezember 2008 E. 3.2).
3.2 Ob eine Rechtsstreitigkeit einem internationalen Schiedsgericht mit Sitz in der Schweiz zur Beurteilung unterbreitet werden kann, beurteilt sich - wie der Beschwerdeführer zutreffend vorbringt - nach <ref-law>. Danach kann jeder vermögensrechtliche Anspruch Gegenstand eines Schiedsverfahrens sein. Die Bestimmung enthält eine materielle Regelung der Schiedsfähigkeit; auf die Aufnahme einer Kollisionsnorm hat der Gesetzgeber bewusst verzichtet, um die mit einer solchen Lösung verbundenen Schwierigkeiten bei der Bestimmung des anwendbaren Rechts zu vermeiden (BGE <ref-ruling> E. 3a S. 355).
Bei den mit der Schiedsklage geltend gemachten Geldforderungen infolge Verletzung des Arbeitsvertrags handelt es sich um vermögensrechtliche Ansprüche im Sinne von <ref-law>, was auch die Beschwerdegegnerin vor Bundesgericht nicht in Abrede stellt. Sie bringt jedoch vor, Art. 19 Abs. 1 bZPO, nach dem arbeitsrechtliche Streitigkeiten nicht von Schiedsgerichten beurteilt werden können, sei im konkreten Fall als Teil des bulgarischen Ordre public zu beachten und verbiete die Anrufung eines Schiedsgerichts.
3.3 Das Bundesgericht hat in seiner Rechtsprechung zwar die Möglichkeit in Betracht gezogen, die Schiedsfähigkeit eines konkreten Rechtsstreits gegebenenfalls mit Blick auf Bestimmungen zu verneinen, die zwingend die staatliche Gerichtsbarkeit vorschreiben und deren Beachtung unter dem Blickwinkel des Ordre public (<ref-law>) geboten ist (BGE <ref-ruling> E. 3c S. 357; Urteile 4A_654/2011 vom 23. Mai 2012 E. 3.4; 4A_370/2007 vom 21. Februar 2008 E. 5.2.2). Dies kann entgegen dem angefochtenen Entscheid allerdings nicht dahingehend verstanden werden, dass ohne Weiteres zwingende Bestimmungen einer ausländischen Rechtsordnung zu berücksichtigen wären, mit welcher die Rechtsstreitigkeit Verbindungen aufweist, und die den Begriff der Schiedsfähigkeit möglicherweise enger fassen (vgl. <ref-ruling> E. 5c/aa S. 196).
Dem TAS kann insoweit nicht gefolgt werden, als es seinen Nichteintretensentscheid mit der fehlenden Schiedsfähigkeit der eingeklagten Ansprüche begründet. Zudem hat es im Rahmen der Zuständigkeitsfrage zu Unrecht berücksichtigt, es bestehe aufgrund von Art. 19 bZPO und Art. V Abs. 2 lit. a des New Yorker Übereinkommens vom 10. Juni 1958 über die Anerkennung und Vollstreckung ausländischer Schiedssprüche (SR 0.277.12) die Gefahr, dass ein Schiedsentscheid des TAS in Bulgarien nicht durchgesetzt werden könne. Dass Entscheide internationaler Schiedsgerichte mit Sitz in der Schweiz, die gestützt auf <ref-law> einen Rechtsstreit als schiedsfähig erachtet haben, in einem bestimmten Land gegebenenfalls nicht vollstreckt werden können, ist nach dem Willen des Gesetzgebers, der sich ganz bewusst für eine materielle Regelung der Schiedsfähigkeit ausgesprochen hat, hinzunehmen; es ist mithin Sache der Parteien, ein solches Risiko abzuwägen (BGE <ref-ruling> E. 3c S. 357 und E. 3d S. 358; Urteil 4A_654/2011 vom 23. Mai 2012 E. 3.4; vgl. auch <ref-ruling> E. 5c/aa S. 196; vgl. bereits die Botschaft vom 10. November 1982 zum Bundesgesetz über das internationale Privatrecht, BBl 1983 I 460). Abgesehen davon kann das Schiedsgericht im Erkenntnisverfahren ohnehin nicht mit Sicherheit vorhersehen, in welchem Staat eine Partei dereinst die Vollstreckung des Schiedsentscheids verlangen wird (vgl. BERNHARD BERGER/FRANZ KELLERHALS, International and Domestic Arbitration in Switzerland, 2. Aufl. 2010, Rz. 179, 256; BBl 1983 I 460).
3.4 Der angefochtene Entscheid, mit dem sich das angerufene Schiedsgericht für unzuständig erachtet hat, ist allerdings im Ergebnis nicht zu beanstanden. Die Beschwerdegegnerin hat das gültige Zustandekommen einer Schiedsvereinbarung im Schiedsverfahren bestritten und beruft sich auch vor Bundesgericht zu Recht auf die Ungültigkeit der Schiedsklausel.
3.4.1 Die Gültigkeit einer Schiedsvereinbarung beurteilt sich gemäss <ref-law> in inhaltlicher Hinsicht nach dem von den Parteien gewählten, dem auf die Streitsache, insbesondere dem auf den Hauptvertrag anwendbaren oder dem schweizerischen Recht. Soweit der Verweis auf die Bestimmungen des bulgarischen Rechts in Ziffer 16 des Arbeitsvertrags als Rechtswahl hinsichtlich des Zustandekommens der Schiedsklausel verstanden wird und auf den Arbeitsvertrag bulgarisches Recht anwendbar ist, wie dies in der Beschwerdeantwort vorgebracht wird, ist angesichts der zwingenden Bestimmungen über den Abschluss von Schiedsvereinbarungen mit der Beschwerdegegnerin von der Ungültigkeit der Schiedsklausel auszugehen. Zu Recht bringt auch der Beschwerdeführer nicht vor, das bulgarische Recht sei hinsichtlich der materiellen Gültigkeit der Schiedsklausel vorteilhafter, sondern beruft sich ausschliesslich auf deren Gültigkeit nach schweizerischem Recht.
3.4.2 Unter einer Schiedsvereinbarung ist eine Übereinkunft zu verstehen, mit der sich zwei oder mehrere bestimmte oder bestimmbare Parteien einigen, eine oder mehrere, bestehende oder künftige Streitigkeiten verbindlich unter Ausschluss der ursprünglichen staatlichen Gerichtsbarkeit einem Schiedsgericht nach Massgabe einer unmittelbar oder mittelbar bestimmten rechtlichen Ordnung zu unterstellen (<ref-ruling> E. 3.1 S. 70). Entscheidend ist, dass der Wille der Parteien zum Ausdruck kommt, über bestimmte Streitigkeiten ein Schiedsgericht, d.h. ein nichtstaatliches Gericht, entscheiden zu lassen (<ref-ruling> E. 2.2.3 S. 35; <ref-ruling> E. 2.3 S. 679 f.).
Steht - wie im vorliegenden Fall - bezüglich der Schiedsvereinbarung kein tatsächlich übereinstimmender Wille der Parteien fest, so ist diese nach dem Vertrauensprinzip auszulegen, d.h. der mutmassliche Wille ist so zu ermitteln, wie er vom jeweiligen Erklärungsempfänger nach Treu und Glauben verstanden werden durfte und musste (<ref-ruling> E. 2.2.3 S. 35 f.; <ref-ruling> E. 3.2 S. 71; <ref-ruling> E. 2.3 S. 680). Bei der Auslegung einer Schiedsvereinbarung ist deren Rechtsnatur zu berücksichtigen; insbesondere ist zu beachten, dass mit dem Verzicht auf ein staatliches Gericht die Rechtsmittelwege stark eingeschränkt werden. Ein solcher Verzichtswille kann nach bundesgerichtlicher Rechtsprechung nicht leichthin angenommen werden, weshalb im Zweifelsfall eine restriktive Auslegung geboten ist (vgl. <ref-ruling> E. 2.3.1 S. 36 f.; <ref-ruling> E. 2.3 S. 680 f.; <ref-ruling> S. 58 E. 2c/aa). Steht demgegenüber als Auslegungsergebnis fest, dass die Parteien die Streitsache von der staatlichen Gerichtsbarkeit ausnehmen und einer Entscheidung durch ein Schiedsgericht unterstellen wollten, bestehen jedoch Differenzen hinsichtlich der Abwicklung des Schiedsverfahrens, greift grundsätzlich der Utilitätsgedanke Platz; danach ist möglichst ein Vertragsverständnis zu suchen, das die Schiedsvereinbarung bestehen lässt (<ref-ruling> E. 2.2.3 S. 36; <ref-ruling> E. 3.2 S. 71 f.; <ref-ruling> E. 2.3 S. 681).
3.4.3 Ziffer 16 des Arbeitsvertrags hält einerseits fest, dass die Parteien im Falle des Scheiterns einer gütlichen Einigung allfällige Streitigkeiten dem zuständigen Gericht unterbreiten ("the dispute shall be referred for resolving by the competent court"). Ein Ausschluss der staatlichen Gerichtsbarkeit lässt sich daraus nicht entnehmen; im Gegenteil spricht die allgemeine Formulierung für die Beibehaltung der staatlichen Gerichtsbarkeit. Die Parteien anerkennen zwar in der gleichen Vertragsklausel die Zuständigkeit des TAS ("The parties to the contract recognize the Court of Arbitration for Sport ..."), verweisen jedoch gleichzeitig auf die Bestimmungen des bulgarischen Rechts ("... as in this case ... the provisions of Bulgarian legislation will apply"), das ein Schiedsverfahren nicht zulässt, sondern zwingend von der staatlichen Gerichtsbarkeit ausgeht. Es erscheint daher zumindest als fraglich, ob sich der vertraglichen Abmachung nach dem Vertrauensprinzip ein hinreichend klarer Wille entnehmen lässt, Streitsachen aus dem Vertrag von der staatlichen Gerichtsbarkeit auszunehmen und einer Entscheidung durch ein Schiedsgericht zu unterstellen (vgl. auch Urteil 4A_244/2012 vom 17. Januar 2013 E. 4.4). Dass die Vertragsklausel von Ziffer 16 nach Treu und Glauben auf den mutmasslichen Willen der Parteien schliessen liesse, dem Kläger wahlweise den Rechtsweg an das TAS oder die staatlichen Gerichte in Bulgarien zu eröffnen, macht der Beschwerdeführer zu Recht nicht geltend. Der Utilitätsgedanke, nach dem möglichst ein Vertragsverständnis zu suchen ist, das die Schiedsvereinbarung bestehen lässt, greift im Übrigen erst, wenn als Auslegungsergebnis feststeht, dass die Parteien die Streitsache von der staatlichen Gerichtsbarkeit ausnehmen wollten (<ref-ruling> E. 2.2.3 S. 36; <ref-ruling> E. 3.2 S. 71 f.; je mit Hinweisen).
Der Beschwerdeführer hat bei den staatlichen Gerichten in Bulgarien zwei Klagen gegen die Beschwerdegegnerin eingereicht, mit denen er Ansprüche aus dem Arbeitsvertrag vom 11. Januar 2008 geltend macht; er hat mit seinem Vorgehen zu erkennen gegeben, dass er selbst von der Beibehaltung der staatlichen Gerichtsbarkeit ausgegangen war. Darauf, dass die Vertragspartnerin eine Vereinbarung nach Treu und Glauben in einem gewissen Sinne hätte verstehen müssen, darf sich die Gegenpartei jedoch nur berufen, soweit sie selbst die Bestimmung tatsächlich so verstanden hat (vgl. <ref-ruling> E. 3a S. 19; Urteile 4A_538/2011 vom 9. März 2012 E. 2.2; 4A_219/2010 vom 28. September 2010 E. 1, nicht publ. in: <ref-ruling>; KRAMER, in: Berner Kommentar, 1986, N. 122 ff. und N. 146 zu <ref-law>). Der Beschwerdeführer kann sich daher nach Treu und Glauben nicht auf ein Auslegungsergebnis berufen, das gar nicht seinem damaligen Vertragsverständnis entspricht.
Eine Auslegung von Ziffer 16 des Arbeitsvertrags nach dem Vertrauensprinzip kann somit nicht zum Ausschluss der staatlichen Gerichtsbarkeit zugunsten eines Schiedsgerichts und damit zur Wirksamkeit der Schiedsklausel führen. Entsprechend hat das TAS seine Zuständigkeit im Ergebnis zu Recht verneint.
4. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 5'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 18. März 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann