Sachverhalt:
A. Der am 12. September 1997 geborene A._ (Beschwerdeführer) ist ein Kart-Fahrer polnischer Nationalität. Er ist Mitglied des Y._ Racing Club, der dem Polnischen Motorsportverband angehört. Dieser ist wiederum Mitglied der Fédération X._ mit Sitz in Z._ (Beschwerdegegnerin).
Vom 16. bis 18. Juli 2010 nahm der damals 12-jährige Beschwerdeführer, der über eine Lizenz als Kart-Fahrer des Polnischen Motorsportverbandes und der X._ verfügt, an einem Rennen im Rahmen der deutschen Junioren-Kart-Meisterschaft in Q._ (Deutschland) teil und belegte dabei den zweiten Platz.
Am 18. Juli 2010 wurde er einer Doping-Wettbewerbskontrolle unterzogen, die durch die deutsche Nationale Anti-Doping Agentur (NADA) auf Ersuchen des Deutschen Motorsportbundes (DMSB) vorgenommen wurde, der seinerseits Mitglied der X._ ist. Das Labor stellte dabei das Vorhandensein der verbotenen Substanz "Nikethamide" fest, was in der Folge durch eine B-Probe bestätigt wurde.
B. B.a Am 11. Oktober 2010 führte die Medizinische Kommission des X._-Anti-Doping-Ausschusses in Z._ eine Verhandlung durch. Mit Entscheid vom gleichen Tag verhängte die Kommission über den Beschwerdeführer eine Wettkampfsperre von 2 Jahren, beginnend am 18. Juli 2010 und endend am 18. Juli 2012. Ausserdem disqualifizierte die Kommission den Beschwerdeführer vom Rennen in Q._ am 18. Juli 2010 und aberkannte alle seit diesem Datum erzielten Resultate und Wettkampfpreise.
B.b Gegen den Entscheid der Medizinischen Kommission des X._-Anti-Doping-Ausschusses legte der Beschwerdeführer Berufung beim TAS ein.
Mit Urteil vom 15. September 2011 (CAS 2010/A/2268) hiess das TAS die Berufung teilweise gut (Ziff. 1), hob den Entscheid der Medizinischen Kommission des X._-Anti-Doping-Ausschusses vom 11. Oktober 2010 auf (Ziff. 2) und verhängte über den Beschwerdeführer eine Wettkampfsperre von 18 Monaten, beginnend am 18. Juli 2010 (Ziff. 3). Weiter disqualifizierte das TAS den Beschwerdeführer vom Rennen in Q._ am 18. Juli 2010 und aberkannte alle seit diesem Datum erzielten Resultate und Wettkampfpreise (Ziff. 4). Die Kanzleikosten von Fr. 500.-- auferlegte das TAS dem Beschwerdeführer; im Übrigen verzichtete es auf die Erhebung von Gerichtskosten (Ziff. 5) und schlug die Parteikosten wett (Ziff. 6).
C. Mit Beschwerde in Zivilsachen vom 17. Oktober 2011 beantragt der Beschwerdeführer dem Bundesgericht, es sei das Urteil des TAS vom 15. September 2011 (CAS 2010/A/2268) vollumfänglich aufzuheben. Eventualiter seien die Ziff. 3 (Sperre) und die Ziff. 4 betreffend die Annullierung aller anderen Rennresultate, soweit sie nicht das Rennen in Q._, Deutschland, vom 18. Juli 2010 betreffen, sowie die Ziff. 5 - 6 (Kosten- und Entschädigungsfolgen) des angefochtenen Entscheids aufzuheben. Subeventualiter sei der angefochtene Entscheid aufzuheben und die Sache an das TAS zu neuer Entscheidung zurückzuweisen.
Am 7. November 2011 reichte der Beschwerdeführer eine weitere Beschwerdeeingabe mit identischen Beschwerdeanträgen sowie dem Verfahrensantrag ein, dass die vorliegende Eingabe jene vom 17. Oktober 2011 ersetze, falls sie vom Bundesgericht als fristgerecht erhoben qualifiziert werde. Ansonsten werde an der Beschwerde vom 17. Oktober 2011 festgehalten.
Der Beschwerdegegner beantragt in seiner Vernehmlassung vom 12. Dezember 2011 die Abweisung der Beschwerde, soweit Eintreten. Die Vorinstanz beantragt in ihrer Vernehmlassung vom 26. Januar 2012 die Abweisung der Beschwerde. Die Parteien reichten Replik und Duplik ein.
Die Akten des Schiedsverfahrens wurden beigezogen.

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. Beide Parteien hatten im relevanten Zeitpunkt ihren Sitz 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.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Beide Parteien hatten im relevanten Zeitpunkt ihren Sitz 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 2.2.1 Die Beschwerde gegen einen Entscheid ist innert 30 Tagen nach der Eröffnung der vollständigen Ausfertigung beim Bundesgericht einzureichen (<ref-law>). Diese Frist, die nicht erstreckbar ist (<ref-law>), gilt auch für die Einreichung von ergänzenden Beschwerdeeingaben.
Gemäss bundesgerichtlicher Rechtsprechung ist für die Auslösung der Beschwerdefrist gegen Entscheide des TAS nicht die Eröffnung per Fax, sondern die Eröffnung per Post massgebend (Urteil 4A_392/2010 vom 12. Januar 2011 E. 2.3.2).
2.2.2 Der angefochtene Entscheid datiert vom 15. September 2011 und wurde dem Beschwerdeführer am gleichen Tag per Fax zugestellt. Die Zustellung per Post erfolgte indessen erst am 6. Oktober 2011. Somit ist die am 7. November 2011 eingereichte Beschwerdeeingabe rechtzeitig erfolgt (Art. 44 Abs. 1 i.V.m. <ref-law>). Entsprechend der darin enthaltenen Erklärung, wonach bei fristgerechter Einreichung der zweiten Eingabe auf diese abzustellen sei, ist vorliegend ausschliesslich die Beschwerdeschrift vom 7. November 2011 zu beurteilen.
2.2.2 Der angefochtene Entscheid datiert vom 15. September 2011 und wurde dem Beschwerdeführer am gleichen Tag per Fax zugestellt. Die Zustellung per Post erfolgte indessen erst am 6. Oktober 2011. Somit ist die am 7. November 2011 eingereichte Beschwerdeeingabe rechtzeitig erfolgt (Art. 44 Abs. 1 i.V.m. <ref-law>). Entsprechend der darin enthaltenen Erklärung, wonach bei fristgerechter Einreichung der zweiten Eingabe auf diese abzustellen sei, ist vorliegend ausschliesslich die Beschwerdeschrift vom 7. November 2011 zu beurteilen.
2.3 2.3.1 Auf eine Beschwerde kann nur eingetreten werden, wenn der Beschwerdeführer ein schutzwürdiges, mithin ein aktuelles und praktisches Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (<ref-law>; vgl. <ref-ruling> E. 1.1 S. 425 f.; <ref-ruling> E. 1b S. 431). Auf das Erfordernis des aktuellen praktischen Interesses verzichtet das Bundesgericht ausnahmsweise, wenn sich die aufgeworfenen Fragen jederzeit unter gleichen oder ähnlichen Umständen wieder stellen können, an deren Beantwortung wegen ihrer grundsätzlichen Bedeutung ein hinreichendes öffentliches Interesse besteht und eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre (<ref-ruling> E. 2.2; <ref-ruling> E. 2.2 S. 434; <ref-ruling> E. 1.1). Liegt das praktische Interesse im Zeitpunkt der Beschwerdeerhebung vor, fällt es aber nachträglich weg, ist der Rechtsstreit gemäss <ref-law> (SR 273) in Verbindung mit <ref-law> als erledigt abzuschreiben.
Das Bundesgericht prüft grundsätzlich von Amtes wegen, ob auf eine Beschwerde eingetreten werden kann (<ref-law>). Immerhin ist die Beschwerde hinreichend zu begründen (Art. 42 Abs. 1 und 2 BGG), wobei der Beschwerdeführer auch darzulegen hat, dass die gesetzlichen Voraussetzungen des Beschwerderechts nach <ref-law> gegeben sind. Soweit diese nicht ohne weiteres ersichtlich sind, ist es nicht Aufgabe des Bundesgerichts, anhand der Akten oder weiterer, noch beizuziehender Unterlagen nachzuforschen, ob und inwiefern die Beschwerde zulässig ist (vgl. <ref-ruling> E. 1 S. 356, 400 E. 2 S. 404; Urteil 4A_566/2009 vom 22. März 2010 E. 1.2, publ. in: ASA Bulletin 2/2011, S. 433 ff., 435).
2.3.2 Die vorliegende Beschwerde in Zivilsachen hat keine aufschiebende Wirkung (<ref-law>). Ein Gesuch um Erteilung der aufschiebenden Wirkung hat der Beschwerdeführer nicht gestellt. Die ihm in Dispositiv-Ziffer 3 des angefochtenen Entscheids auferlegte Wettkampfsperre lief damit am 18. Januar 2012 ab und der Beschwerdeführer kann seither wieder an Wettkämpfen teilnehmen. Mit der dem Bundesgericht beantragten Aufhebung von Ziff. 3 des angefochtenen Entscheids würde der Beschwerdeführer in keine andere Situation versetzt. Ein persönliches, aktuelles und praktisches Interesse an der Aufhebung der in der Zwischenzeit abgelaufenen Wettkampfsperre ist damit grundsätzlich nicht ersichtlich.
In seiner Eingabe an das Bundesgericht begründet der Beschwerdeführer seine Beschwerdelegitimation denn auch ausschliesslich damit, dass er aufgrund des angefochtenen Urteils für die Ausübung seines Sports gesperrt bleibe. Dass er nebst der (kraft Zeitablaufs bereits erfolgten) Beseitigung der Wettkampfsperre ein schutzwürdiges Interesse an der Aufhebung des angefochtenen Entscheids hätte, legt er in keiner Weise dar und macht auch nicht geltend, dass an der Beantwortung der Fragen wegen grundsätzlicher Bedeutung ein hinreichendes öffentliches Interesse bestünde und eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre. Die Beschwerde ist damit aufgrund des Wegfalls der Beschwerdelegitimation gegenstandslos geworden, soweit sie sich gegen Ziff. 3 des angefochtenen Entscheids (Wettkampfsperre) richtet.
2.3.3 Mit Ziff. 4 des angefochtenen Entscheids hat die Vorinstanz den Beschwerdeführer vom Rennen in Q._ am 18. Juli 2010 disqualifiziert und alle seit diesem Datum erzielten Resultate und Wettkampfpreise aberkannt (Ziff. 4).
An der Aufhebung der Disqualifikation vom Rennen in Q._ am 18. Juli 2010, hat der Beschwerdeführer nach wie vor ein aktuelles und praktisches Interesse, belegte er doch dort gemäss den verbindlichen Sachverhaltsfeststellungen der Vorinstanz (<ref-law>) den zweiten Platz (vgl. auch Urteil 4A_456/2009 vom 3. Mai 2010 E. 2.2, publ. in: ASA Bulletin 2010, S. 786 ff., 789).
In Bezug auf die Aberkennung aller seit diesem Datum erzielten Resultate und Wettkampfpreise ist ein aktuelles und praktisches Aufhebungsinteresse des Beschwerdeführers indessen nicht ersichtlich. Denn weder aus dem angefochtenen Entscheid noch aus den Parteieingaben geht hervor, dass der Beschwerdeführer seit dem Rennen in Q._ bis zum Ablauf der Wettkampfsperre im Januar 2012 an weiteren Wettkämpfen teilgenommen, geschweige denn aberkennungsfähige Resultate erzielt hätte. Der Beschwerdeführer macht denn auch nicht geltend, dass er seither weitere Rennen gefahren wäre. Künftige Resultate unterliegen demgegenüber aufgrund des Ablaufs der Sperre nicht mehr der Aberkennung gemäss Ziff. 4 des angefochtenen Entscheids. Die Beschwerde ist damit ebenfalls unzulässig, soweit sie sich gegen die Aberkennung aller seit dem Rennen in Q._ vom 18. Juli 2010 erzielten Resultate und Wettkampfpreise richtet (Ziff. 4).
2.4 Im Rahmen einer Beschwerde nach <ref-law> sind allein die Rügen zulässig, 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 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
Der Beschwerdeführer formuliert seine Rügen einzig gegen die ihm auferlegte Wettkampfsperre. Gegen die Disqualifikation vom Rennen in Q._ am 18. Juli 2010, gegen die er zur Beschwerde legitimiert wäre, trägt der Beschwerdeführer indessen keine Rügen vor. Vielmehr anerkennt er, dass es im vorliegenden Fall "absolut korrekt" sei, "dass der Beschwerdeführer vom Rennen in Q._ ausgeschlossen worden ist, zumal er in seinem Körper Substanzen hatte, deren Verwendung im sportlichen Wettkampf nicht erlaubt ist, weil dadurch das sportliche Gleichgewicht verzerrt werden könnte" (Beschwerde, S. 14, Rz. 35). Auf die Beschwerde gegen die Disqualifikation vom Rennen in Q._ am 18. Juli 2010 ist damit mangels tauglicher und begründeter Rügen nicht einzutreten.
3. Ist ein Beschwerdeführer zur Anfechtung in der Sache selber nicht legitimiert oder hat er kein aktuelles Interesse mehr an der Anfechtung des Hauptsachenentscheids, kann er dennoch gegen den Kostenentscheid Beschwerde führen, da er durch diesen persönlich und unmittelbar in seinen Interessen betroffen wird (<ref-ruling> E. 1b S. 255; Urteile 4A_604/2010 vom 11. April 2011 E. 1.2; 4A_352/2011 vom 5. August 2011 E. 2). Die Belastung mit Kosten verschafft ihm indes keine Möglichkeit, indirekt über den Kostenentscheid eine Überprüfung des Entscheids in der Hauptsache zu erlangen (<ref-ruling> E. 4 S. 299). Daher kann er nur geltend machen, die Kostenverlegung sei aus einem anderen Grund als dem blossen Umstand, dass er in der Hauptsache unterlag, rechtswidrig (<ref-ruling>; Urteil 4A_352/2011 vom 5. August 2011 E. 2), wobei im vorliegenden Fall von vornherein nur die Rügen gemäss <ref-law> in Betracht fallen.
Da der Beschwerdeführer gegen den vorinstanzlichen Kostenentscheid keine entsprechenden Rügen erhebt, ist auch auf die Beschwerde gegen die Ziff. 5 und 6 des angefochtenen Entscheids nicht einzutreten.
4. Nach dem Gesagten ist auf die Beschwerde nicht einzutreten, soweit sie sich nicht als gegenstandslos erweist.
Die Gerichtskosten werden in der Regel der unterliegenden Partei auferlegt (<ref-law>). Soweit die Beschwerde gegenstandslos geworden ist, richtet sich der Entscheid über die Prozesskosten des bundesgerichtlichen Verfahrens jedoch nach <ref-law> in Verbindung mit <ref-law>. Dieser Vorschrift zufolge entscheidet das Gericht mit summarischer Begründung über die Prozesskosten auf Grund der Sachlage vor Eintritt des Erledigungsgrundes. Lässt sich der mutmassliche Ausgang des Verfahrens im konkreten Fall nicht ohne weiteres feststellen, so sind allgemeine prozessrechtliche Kriterien heranzuziehen: Danach wird diejenige Partei kosten- und entschädigungspflichtig, die das gegenstandslos gewordene Verfahren veranlasst hat oder bei der die Gründe eingetreten sind, die zur Gegenstandslosigkeit des Prozesses geführt haben (<ref-ruling> E. 4a S. 494).
Da der Beschwerdeführer das gegenstandslos gewordene Verfahren veranlasst hat und sich vorliegend nicht ohne weiteres beurteilen lässt, ob den Rügen gegen die Wettkampfsperre Erfolg beschieden gewesen wären, wird der Beschwerdeführer kosten- und entschädigungspflichtig.

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten, soweit sie nicht gegenstandslos geworden ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 18. Juni 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Hurni