Sachverhalt:
A. A.a A._ (Beschwerdeführer) mit Wohnsitz in D._ ist professioneller Eishockeyspieler. Er nahm mit der deutschen Eishockey-Nationalmannschaft an verschiedenen internationalen Wettkämpfen teil, so unter anderem an den Eishockey-Weltmeisterschaften in den Jahren 2003, 2004, 2006, 2007 und 2008 sowie an den Olympischen Winterspielen in Turin im Jahr 2006.
Die Welt-Anti-Doping-Agentur (WADA) (Beschwerdegegnerin) ist eine Stiftung schweizerischen Rechts mit Sitz in Lausanne. Ihr Zweck ist der weltweite Kampf gegen Doping im Sport.
Die International Ice Hockey Federation (IIHF) ist der internationale Eishockeyverband mit Sitz in Zürich.
A.b Am 6. März 2008 um 12.30 Uhr erschien Herr B._ im Auftrag der deutschen Nationalen Anti-Doping-Agentur (NADA) am Wohnsitz des Beschwerdeführers, um eine unangemeldete Probe ("out-of-competition sample collection"; "Trainingsprobe") vorzunehmen. Nach Darstellung der Beschwerdegegnerin weigerte sich der Beschwerdeführer, auch nachdem er vom Dopingkontrolleur auf die schwerwiegenden disziplinarischen Sanktionen hingewiesen worden sei, die Kontrolle durchzuführen. Unstreitig ist, dass der Dopingkontrolleur die Wohnung des Beschwerdeführers um 12.50 Uhr unverrichteter Dinge verliess.
Vier Minuten später meldete sich der Beschwerdeführer telefonisch bei der NADA und informierte sie über den Vorfall. Um 14.16 Uhr rief er nochmals bei der NADA an und erklärte, er wolle sich einer Probenahme unterziehen, worauf ihm die NADA mitteilte, eine Wiederholung der Kontrolle sei nicht möglich. In der Folge fand auf seine Initiative hin noch am gleichen Tag um 17.00 Uhr eine Dopingkontrolle statt, die vom Deutschen Eishockey-Bund (DEB) organisiert und von Herrn B._ durchgeführt wurde. Die Probe wurde vom Institut für Dopinganalytik und Sportbiochemie Dresden analysiert; dabei liessen sich keine verbotenen Wirkstoffe oder unzulässigen Methoden nachweisen.
A.c Am 7. März 2008 informierte die NADA den Deutschen Eishockey-Bund über den Vorfall. Am 19. März 2008 teilte dieser der NADA seine Absicht mit, den Beschwerdeführer öffentlich zu verwarnen. Die NADA wiederum wies den DEB darauf hin, dass die Verweigerung einer Probenahme einen Verstoss gegen Artikel 2.3 des NADA Code (NADC) bedeute, der mit Artikel 2.3 des WADA Code (WADC) übereinstimmt, und entsprechend zu sanktionieren sei.
Der DEB informierte die NADA, dass die im NADC bzw. WADC vorgesehenen Sanktionen übermässig seien und angesichts der Umstände des konkreten Falls eine öffentliche Verwarnung ausreiche. Entsprechend sprach er am 15. April 2008 eine öffentliche Verwarnung gegen den Spieler aus und bestrafte ihn mit einer Busse von EUR 5'000.-- sowie 56 Stunden gemeinnützige Arbeit.
NADA nahm vom Entscheid des DEB über die Medien Kenntnis und erfuhr dabei auch, dass die IIHF diesen unterstützte und den Spieler an der Eishockey-Weltmeisterschaft in Kanada vom 2. - 11. Mai 2008 würde spielen lassen. Die NADA informierte daher am 21. April 2008 die Beschwerdegegnerin, damit diese Massnahmen ergreifen konnte.
Mit Schreiben vom 6. Mai 2008 ersuchte die Beschwerdegegnerin gestützt auf Artikel 3.1 der IIHF-Disziplinarordnung 2004 (Disciplinary Regulations) einerseits das Direktorium der IIHF-Weltmeisterschaften, den Beschwerdeführer ab 6. Mai 2008 einstweilig zu suspendieren und andererseits die IIHF, innert 48 Stunden einen Entscheid über die vorläufige Suspendierung zu fällen. Im Weiteren forderte die Beschwerdegegnerin die IIHF-Disziplinarkommission (Disciplinary Committee) auf, ein Disziplinarverfahren gegen den Beschwerdeführer einzuleiten und ihn mit einer zweijährigen Spielsperre zu belegen.
Das Präsidium der IIHF teilte der Beschwerdegegnerin mit E-Mail vom 7. Mai 2008 mit, dass sie nicht in der Lage sei, dem Antrag entsprechend tätig zu werden. Die IIHF wies unter anderem darauf hin, dass die vom Deutschen Eishockey-Bund eingesetzte interne Disziplinarkommission am 15. April 2008 einen Entscheid in der Sache gefällt habe und die Rechtsmittelfrist noch laufe.
Die Beschwerdegegnerin schrieb der IIHF gleichentags, sie gehe davon aus, dass es sich beim Schreiben vom 7. Mai 2008 um eine Entscheidung im Sinne der IIHF-Disziplinarordnung handle, die einem Weiterzug an das Tribunal Arbitral du Sport (TAS) unterliege.
A.d Am 9. Mai 2008 focht die Beschwerdegegnerin den Entscheid des DEB vom 15. April 2008 beim Ad-hoc-Schiedsgericht des Deutschen Olympischen Sportbundes an und beantragte, der Entscheid sei aufzuheben und es sei gegen den Spieler eine zweijährige Spielsperre zu verhängen.
Das Ad-hoc-Schiedsgericht wies die Beschwerde mit Entscheid vom 3. Dezember 2008 ab, da es für die von der Beschwerdegegnerin beantragte Sanktion an einer rechtlichen Grundlage fehle.
B. Am 27. Mai 2008 appellierte die Beschwerdegegnerin beim TAS gegen das Schreiben der IIHF vom 7. Mai 2008 und beantragte, es sei eine zweijährige Spielsperre zu verhängen (Verfahren CAS 2008/A/1564). Sie wies darauf hin, dass die Schiedsklage zur Wahrung ihrer Rechte erfolge, insbesondere für den Fall, dass die beim deutschen Ad-hoc-Schiedsgericht eingereichte Klage nicht zugelassen würde. Das Verfahren wurde daraufhin bis zum Entscheid des deutschen Schiedsgerichts sistiert.
In der Folge focht die Beschwerdegegnerin auch den Entscheid des Ad-hoc-Schiedsgerichts des Deutschen Olympischen Sportbundes beim TAS an (Verfahren CAS 2008/A/1738). Das TAS trat darauf jedoch mit Entscheid vom 23. Juni 2009 mangels Zuständigkeit nicht ein.
Die IIHF verzichtete auf eine Teilnahme am Schiedsverfahren. Der Beschwerdeführer erhob unter anderem die Einrede der Unzuständigkeit, da es an einer Schiedsvereinbarung fehle.
C. Das TAS erachtete sich hinsichtlich des zuerst erhobenen Appeal (Verfahren CAS 2008/A/1564) gestützt auf das vom Beschwerdeführer jeweils im Hinblick auf die Weltmeisterschaft unterzeichnete "Player Entry Form" für zuständig und sah das E-Mail des IIHF vom 7. Mai 2008 als anfechtbaren Entscheid an. Es hob den Entscheid der IIHF mit Schiedsspruch vom 23. Juni 2009 auf und verhängte gegen den Beschwerdeführer eine zweijährige Spielsperre.
D. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, der Schiedsspruch des TAS vom 23. Juni 2009 (Verfahren CAS 2008/A/1564) sei aufzuheben.
Sowohl die Beschwerdegegnerin als auch die Vorinstanz schliessen auf Abweisung der Beschwerde. Der Beschwerdeführer hat dem Bundesgericht eine Replik eingereicht.
E. Mit Verfügung vom 7. September 2009 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung erteilt.

Erwägungen:
1. Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel derjenigen des angefochtenen Entscheids. Wurde dieser Entscheid in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht verschiedener Sprachen bedienen, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde.
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. Der Beschwerdeführer hatte im relevanten Zeitpunkt weder seinen Wohnsitz noch seinen gewöhnlichen Aufenthalt in 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 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 mit Hinweis).
2.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von Art. 105 Abs. 2 sowie Art. 97 BGG ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733; je mit Hinweisen). Neue Tatsachen und Beweismittel dürfen zudem nur insoweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Der Beschwerdeführer stellt seinen rechtlichen Ausführungen eine ausführliche Sachverhaltsdarstellung voran, in der er den Ablauf der Ereignisse sowie des Verfahrens aus seiner Sicht darlegt. Wie die Beschwerdegegnerin zu Recht einwendet, weicht er darin in verschiedenen Punkten von den tatsächlichen Feststellungen der Vorinstanz ab oder erweitert diese, ohne Ausnahmen von der Sachverhaltsbindung gemäss Art. 105 Abs. 2 und Art. 97 Abs. 1 BGG geltend zu machen. Seine Vorbringen haben insoweit unbeachtet zu bleiben. Unbeachtlich sind auch die verschiedenen vom Beschwerdeführer neu eingereichten Beweismittel.
3. Der Beschwerdeführer macht unter Berufung auf <ref-law> geltend, die Vorinstanz habe sich zu Unrecht für zuständig erklärt.
3.1 Die Vorinstanz hat zunächst unter Verweis auf die von der IIHF eingegangene Verpflichtung zur Einhaltung und Umsetzung des WADC, die breite Zweckbestimmung der damals geltenden IIHF-Statuten, die über die Verantwortlichkeit für die IIHF-Meisterschaften hinausgingen, sowie die Mitgliedschaft des DEB bei der IIHF festgehalten, dass der Beschwerdeführer - aus Sicht der Statuten der IIHF - als Spieler zu betrachten sei, der vom DEB für die Teilnahme an einer IIHF-Meisterschaft bzw. Veranstaltung aufgestellt worden und als solcher durch die IIHF-Statuten und Reglemente gebunden sei und die endgültige und verbindliche Entscheidbefugnis der IIHF zu anerkennen habe. Infolgedessen verlange die IIHF anlässlich einer IIHF-Meisterschaft oder IIHF-Veranstaltung von den Spielern die Unterzeichnung eines Anmeldeformulars ("Player Entry Form"), das unter anderem wie folgt lautet:
"I, the undersigned, declare, on my honour that
a) I am under the jurisdiction of the National Association I represent.
a) I am under the jurisdiction of the National Association I represent.
... l) I agree to abide by and observe the IIHF Statutes, By-laws and Regulations (including those related to Medical Doping Control) and the decisions by the IIHF and the Championship Directorate in all matters including disciplinary measures, not to involve any third party whatsoever outside of the IIHF in the resolution of any dispute whatsoever arising in connection with the IIHF Championship and/or the Statutes, By-laws and Regulations and decisions made by the IIHF relating thereto excepting where having exhausted the appeal procedures within the IIHF in which case I undertake to submit any such dispute to the jurisdiction of the Court of Arbitration for Sport (CAS) in Lausanne, Switzerland, for definitive and final resolution."
Die Vorinstanz hat zutreffend festgehalten, dass die erwähnte Schiedsvereinbarung den Voraussetzungen von <ref-law> zu genügen habe und im Übrigen - was von keiner Partei in Frage gestellt wird - schweizerisches Recht für anwendbar erklärt. Sie hat die Erklärung des Beschwerdeführers sodann in Anwendung des Vertrauensprinzips ausgelegt und erwogen, dass die Spieler sich ganz allgemein an die IIHF-Statuten und Reglemente sowie insbesondere die von der IIHF getroffenen Entscheidungen (einschliesslich Disziplinarmassnahmen) gebunden erklärt hätten. Die Verpflichtung, nach Ausschöpfung der internen Rechtsmittel an das TAS zu gelangen, beziehe sich nicht nur auf Streitigkeiten im Zusammenhang mit der IIHF-Meisterschaft, sondern auch auf solche, die nicht notwendigerweise in Verbindung mit der IIHF-Meisterschaft und den damit zusammenhängenden Aspekten der IIHF-Statuten und Reglemente stünden. Dies ergebe sich aus der Verwendung des Wortpaars "and/or" im Text von lit. l sowie aus der allgemeinen Formulierung des Eingangssatzes dieser Klausel. Es bestehe daher kein Anhaltspunkt, der für einen Ausschluss der Zuständigkeit des TAS sprechen würde.
Die Vorinstanz befand zudem, der Umstand, dass der Beschwerdeführer die besagten Anmeldeformulare seit 2003 beinahe jedes Jahr unterzeichnet habe, bedeute nicht, dass die Gültigkeit des Dokuments auf ein Jahr beschränkt sei. Zudem verlange die IIHF dessen wiederholte Unterzeichnung aus administrativen Gründen anlässlich jeder IIHF-Meisterschaft auch von Spielern, die bereits ein solches Formular unterzeichnet hätten, um sicherzustellen, dass alle an der aktuellen IIHF-Meisterschaft das Formular unterzeichnet hätten. Da die IIHF nie wissen könne, ob ein für eine IIHF-Meisterschaft aufgestellter Spieler auch an der folgenden Meisterschaft oder - wegen einer Verletzung oder Leistungsschwäche - erst an einer späteren Meisterschaft teilnehmen werde, könne die IIHF ihrer Verpflichtung zur Vornahme von Trainingskontrollen und Kontrollen ausserhalb der Saison gegenüber der WADA nur nachkommen, wenn einmal für eine IIHF-Meisterschaft aufgestellte Spieler so lange im rechtlichen Zuständigkeitsbereich der IIHF verblieben, als sie für zukünftige Wettkämpfe bzw. Veranstaltungen in Frage kämen.
Nach Ansicht der Vorinstanz erfüllt das vom Beschwerdeführer unterzeichnete Anmeldeformular damit die Anforderungen an eine gültige Schiedsklausel. Das Schreiben der IIHF vom 7. Mai 2008 sei zudem als Entscheidung der IIHF-Disziplinarkommission zu betrachten, weshalb die angerufene Vorinstanz gestützt auf Artikel 3.9 der IIHF-Disziplinarordnung 2004 in Verbindung mit Artikel 47 - 49 der damals geltenden IIHF-Statuten, die eine Beschwerdemöglichkeit an das TAS vorsehen, zur Beurteilung des von der Beschwerdegegnerin erhobenen Appeal zuständig sei. Indem der Beschwerdeführer das Anmeldeformular unterzeichnet habe, insbesondere am 26. April 2007 sowie am 1. Mai 2008, sei er an diese Bestimmungen gebunden.
Nach Ansicht der Vorinstanz erfüllt das vom Beschwerdeführer unterzeichnete Anmeldeformular damit die Anforderungen an eine gültige Schiedsklausel. Das Schreiben der IIHF vom 7. Mai 2008 sei zudem als Entscheidung der IIHF-Disziplinarkommission zu betrachten, weshalb die angerufene Vorinstanz gestützt auf Artikel 3.9 der IIHF-Disziplinarordnung 2004 in Verbindung mit Artikel 47 - 49 der damals geltenden IIHF-Statuten, die eine Beschwerdemöglichkeit an das TAS vorsehen, zur Beurteilung des von der Beschwerdegegnerin erhobenen Appeal zuständig sei. Indem der Beschwerdeführer das Anmeldeformular unterzeichnet habe, insbesondere am 26. April 2007 sowie am 1. Mai 2008, sei er an diese Bestimmungen gebunden.
3.2 3.2.1 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. 3.1 S. 567; <ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733).
3.2.2 Nachdem die Vorinstanz einen wirklichen Willen der Parteien nicht hat feststellen können, hat sie den Inhalt der im unterzeichneten Anmeldeformular enthaltenen Willenserklärung zutreffend nach dem Vertrauensprinzip beurteilt (vgl. <ref-ruling> E. 2.3.2 S. 274 mit Hinweisen). Die Erklärung ist danach so auszulegen, wie sie nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen nach Treu und Glauben verstanden werden durfte und musste (<ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 2.3.2 S. 274 f.; <ref-ruling> E. 3.2 S. 424, 686 E. 4.3.1 S. 689; je mit Hinweisen).
Nach lit. l des Anmeldeformulars unterwirft sich der Spieler für bestimmte Streitigkeiten ("such dispute") der Zuständigkeit des TAS. Auf welche Auseinandersetzungen sich diese Verpflichtung bezieht, wird im vorangehenden Teilsatz umschrieben, nämlich auf jegliche Streitigkeit, die im Zusammenhang mit der IIHF-Meisterschaft und/oder den Statuten, By-laws und Reglementen sowie Entscheidungen der IIHF diesbezüglich entsteht ("the resolution of any dispute whatsoever arising in connection with the IIHF Championship and/or the Statutes, By-laws and Regulations and decisions made by the IIHF relating thereto"). Ausgehend vom Wortlaut spricht die Verwendung des Wortpaars "und/oder", wie die Vorinstanz grundsätzlich zutreffend erkannt hat, zwar dafür, dass die Statuten und Reglemente betreffenden Streitigkeiten auch ohne Zusammenhang mit der jeweiligen IIHF-Meisterschaft dem TAS zu unterbreiten wären. Andererseits ist auch der Einwand des Beschwerdeführers nicht von der Hand zu weisen, dass der Zusatz "relating thereto" als Eingrenzung in dem Sinne verstanden werden kann, dass auch Streitigkeiten betreffend die Statuten, Reglemente und Entscheidungen der IIHF nur dann von der Schiedsklausel erfasst sind, wenn sie mit der IIHF-Meisterschaft im Zusammenhang stehen. Die Frage braucht jedoch nicht vertieft zu werden, da sich die Bedeutung der Erklärung nach Treu und Glauben vorliegend aus dem Zusammenhang erschliesst.
3.2.3 Der Beschwerdeführer hat das Anmeldeformular jeweils im Hinblick auf eine Teilnahme an der IIHF-Weltmeisterschaft unterzeichnet. Das "Player Entry Form" bestand aus einem einseitigen Formular, auf dem zunächst der betreffende IIHF-Wettkampf, dessen Austragungsort und -datum sowie die Mannschaft des Spielers aufgeführt wurden. Teilweise erschien die Bezeichnung des Wettkampfs zudem bereits im Briefkopf (z.B. in den Jahren 2006 und 2007: "IIHF World Championship, MEN") einmal auch mit dem entsprechenden Logo der Weltmeisterschaft (im Jahr 2007: "World Championship Russia"). Im Hauptteil des Formulars sind die persönlichen Daten des Spielers eingetragen, während im Anschluss daran in deutlich verkleinerter und daher nur noch schwer lesbarer Schrift verschiedene Erklärungen, so unter anderem die erwähnte Schiedsklausel, aufgeführt sind.
Unabhängig vom Wortlaut der Klausel durfte der Spieler, der das Anmeldeformular grundsätzlich jährlich wiederkehrend in unregelmässigen Abständen auszufüllen und zu unterzeichnen hatte, davon ausgehen, dass sich seine Erklärungen, wie auch die eingangs aufgeführten Angaben, auf einen bestimmten Wettkampf beziehen. Er musste bei der Unterzeichnung im Hinblick auf eine zeitlich und örtlich genau umschriebene Sportveranstaltung nicht damit rechnen, sich im Kleingedruckten gleichzeitig ganz generell und ohne Zusammenhang mit der konkreten Meisterschaft für jegliche Streitigkeit der Zuständigkeit eines Schiedsgerichts zu unterwerfen. Der Einwand der Beschwerdegegnerin sowie die Begründung der Vorinstanz, eine jährlich wiederkehrende Unterzeichnung sei lediglich aus verwaltungstechnischen Gründen erfolgt, ändere jedoch nichts an der zeitlich und gegenständlich unbeschränkten Geltung, vermögen zudem nicht zu überzeugen. Wesentlich plausibler ist die Auffassung, wonach das Anmeldeformular seinem Zweck, der Bezeichnung als "Player Entry Form" und der Ausrichtung auf ein konkretes Turnier entsprechend, von den jeweils für die Nationalmannschaften aufgestellten Spielern jährlich gerade und ausschliesslich im Hinblick auf die kommende Weltmeisterschaft auszufüllen und zu unterzeichnen war.
Einen Zusammenhang der konkret angeordneten Probeentnahme vom 6. März 2008 sowie der beantragten generellen Spielsperre von zwei Jahren mit der vom 2. - 11. Mai 2008 in Kanada stattfindenden IIHF-Weltmeisterschaft hat die Beschwerdegegnerin nicht aufgezeigt. Nach den Feststellungen im angefochtenen Entscheid war die Kontrolle weder von der WADA noch der IIHF angeordnet worden, wobei sich Letztere in der fraglichen Angelegenheit im Gegenteil für unzuständig erklärt hatte. Die Kontrolle wurde nicht von der WADA, sondern von der NADA durchgeführt und für die Beurteilung des Testresultats war in erster Linie der Deutsche Eishockey-Bund zuständig. Auch der Hinweis der Vorinstanz auf die Verpflichtung der IIHF zur Vornahme von Trainingskontrollen und Kontrollen ausserhalb der Saison gegenüber der WADA vermag daher keinen Zusammenhang mit einem IIHF-Wettkampf zu begründen. Der Beschwerdeführer musste nach Treu und Glauben nicht davon ausgehen, mit der Unterzeichnung des Anmeldeformulars vom 1. Mai 2008 eine Schiedsvereinbarung abzuschliessen, welche die Sanktionierung seines Verhaltens anlässlich der Dopingkontrolle vom 6. März 2008 umfasste, das bereits zur Eröffnung eines Disziplinarverfahrens beim nationalen Verband geführt hatte.
Die vorliegende Streitigkeit über die von der Beschwerdegegnerin beantragte zweijährige Spielsperre im Zusammenhang mit der am 6. März 2008 vorgenommenen Dopingkontrolle der NADA wird von der in lit. l des Anmeldeformulars ("Player Entry Form") enthaltenen Schiedsvereinbarung nicht erfasst. Entgegen dem angefochtenen Entscheid lässt sich die Zuständigkeit der Vorinstanz nicht auf das vom Beschwerdeführer unterzeichnete Anmeldeformular stützen.
3.2.4 Ausser dem Anmeldeformular für die Weltmeisterschaften, das sich unter dem Gesichtspunkt von <ref-law> als unzureichend erwiesen hat, lassen sich den Feststellungen des angefochtenen Entscheids keine Hinweise auf eine im Sinne dieser Bestimmung wirksame Schiedsklausel entnehmen. Die Beschwerdegegnerin bringt in ihrer Antwort in pauschaler Weise vor, der Beschwerdeführer habe mit Unterzeichnung des Anmeldeformulars lediglich einen vorbestehenden Zustand bestätigt, da er dem an der Weltmeisterschaft teilnehmenden nationalen Verband angehöre, der selbst Mitglied des internationalen Verbands IIHF sei. Die Vorinstanz hat jedoch die Bindung des Beschwerdeführers an ihre Entscheidbefugnis auf die Unterzeichnung der IIHF-Anmeldeformulare, insbesondere der Jahre 2007 und 2008, gestützt. Sie hält zwar in ihrer Vernehmlassung fest, dass die IIHF-Statuten und sonstigen IIHF-Regeln, insbesondere Artikel 3.1 der IIHF-Disziplinarordnung 2004 eine weitere Rechtsgrundlage für ihre Zuständigkeit bildeten, stellt für die Bindung des Spielers an diese Bestimmungen jedoch wiederum auf die Unterzeichnung der Anmeldeformulare ab, indem sie dafür hält, dass sich diese zweite Rechtsgrundlage "kaskadenförmig" aus der ersten ableite.
Weder die Vorinstanz noch die Beschwerdegegnerin zeigen konkret auf, inwiefern sich der Beschwerdeführer formgültig und in allgemeiner Weise den IIHF-Statuten und sonstigen Vorschriften, so insbesondere der IIHF-Disziplinarordnung 2004, unterworfen hätte. Zwar ist die Rechtsprechung hinsichtlich der Gültigkeit von Schiedsvereinbarungen im Bereich der internationalen Schiedsgerichtsbarkeit von Grosszügigkeit geprägt, was sich auch in der Beurteilung der Wirksamkeit von Schiedsvereinbarungen mittels Verweisungen zeigt (<ref-ruling> E. 4.3.2.3 S. 244 f. mit Hinweisen). Entsprechend hat das Bundesgericht einen globalen Verweis auf eine in Verbandsstatuten enthaltene Schiedsklausel verschiedentlich als gültig erachtet (Urteile 4A_460/2008 vom 9. Januar 2009 E. 6.2; 4P.253/2003 vom 25. März 2004 E. 5.4; 4P.230/2000 vom 7. Februar 2001 E. 2a; 4C.44/1996 vom 31. Oktober 1996 E. 3c; vgl. auch <ref-ruling> E. 4.3.2.3 S. 245; <ref-ruling> E. 5.3.1 S. 735; je mit Hinweisen). So hat es etwa im Fall eines Fussballspielers, der Mitglied des nationalen Verbands war, die in den Statuten enthaltene Bestimmung, wonach die dem Verband angehörenden Sportler die Regeln der FIFA beachten müssten, als rechtswirksamen Verweis auf die in den FIFA-Statuten enthaltene Schiedsklausel erachtet (Urteil 4A_460/2008 vom 9. Januar 2009 E. 6.2). Den Sachverhaltsfeststellungen des angefochtenen Entscheids lässt sich jedoch nicht entnehmen, dass im zu beurteilenden Fall entsprechende Verhältnisse vorliegen würden.
Eine nach <ref-law> wirksame Schiedsvereinbarung ist entgegen dem angefochtenen Entscheid nicht dargetan. Die Vorinstanz hat sich zur Beurteilung der vorliegenden Streitigkeit daher zu Unrecht gestützt auf das "Player Entry Form" für zuständig erklärt. Es bleibt jedoch offen, ob sich eine Zuständigkeit anhand der im Schiedsverfahren zu berücksichtigenden Vorbringen der Parteien gegebenenfalls auf einen vom Spieler akzeptierten Verweis auf eine in den Verbandsregeln enthaltene Schiedsklausel stützen liesse.
4. Die Beschwerde in Zivilsachen gegen internationale Schiedsentscheide ist - abgesehen von Ausnahmen, deren Voraussetzungen vorliegend nicht erfüllt sind (vgl. BGE <ref-ruling> E. 1b S. 282; <ref-ruling> E. 4 S. 95 f.) - rein kassatorischer Natur (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst). Der Entscheid der Vorinstanz vom 23. Juni 2009 ist demnach in Gutheissung der Beschwerde aufzuheben.
Dem Ausgang des Verfahrens entsprechend wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid der Vorinstanz vom 23. Juni 2009 wird aufgehoben.
2. Die Gerichtskosten von Fr. 5'000.-- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 6'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 6. November 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann