Sachverhalt: A. A.a X._ (Beschwerdeführer) ist ein erfahrener internationaler Springreiter. Die Fédération Equestre Internationale (FEI; Beschwerdegegnerin) ist der Weltverband für den Reitsport mit Sitz in Lausanne. A.b Der Beschwerdeführer nahm zwischen dem 8. und 21. August 2008 mit dem Pferd Y._ als Mitglied des Nationalteams Z._an den Olympischen Sommerspielen 2008 in China teil. Er gewann mit der Springreitermannschaft Z._ die Bronzemedaille. Am 18. August 2008, nach dem Mannschaftsfinal der Springreiter, wurde beim Pferd Y._ eine Urinprobe entnommen. Die Analyse der Urinprobe wurde vom anerkannten FEI-Labor "A._ Laboratory" unter der Aufsicht der Chemikerin B._ sowie des "Chief Racing Chemist" und Vorstehers des genannten Labors, Dr. C._, durchgeführt. Im Urin von Y._ wurde gemäss Testbericht vom 21. August 2008 die verbotene Substanz Capsaicin nachgewiesen. Weder ein Antrag für den Gebrauch von Capsaicin noch ein entsprechendes Medikationsformular waren eingereicht worden. Am 21. August 2008 informierte die Beschwerdegegnerin den Beschwerdeführer über den Nachweis der verbotenen Substanz sowie die mögliche Regelverletzung. Gleichzeitig wurde er provisorisch suspendiert, wobei er die Möglichkeit eingeräumt erhielt, sich anlässlich eines Preliminary Hearing vor dem FEI-Tribunal zu äussern, das noch am selben Tag stattfand. Der Beschwerdeführer bot keine Erklärung für das Vorliegen der verbotenen Substanz an. Der vorläufige Entscheid wurde dem Beschwerdeführer ebenfalls am gleichen Tag mitgeteilt. Danach wurde die provisorische Sperre aufgrund des Nachweises von Capsaicin bis zu einem definitiven Entscheid des FEI-Tribunals aufrechterhalten. Am 21. August 2008 wurde dem Beschwerdeführer auch mitgeteilt, dass die B-Probe im A._ Laboratory analysiert werde. Er wurde zudem über sein Recht informiert, bei der Identifikation sowie beim Öffnen der B-Probe selbst dabei zu sein oder sich vertreten zu lassen. Der Beschwerdeführer nahm zur Kenntnis, dass die B-Probe wie beschrieben analysiert werden soll und teilte mit, er werde sich durch Dr. D._, dem Mannschaftstierarzt des schwedischen Reitsportverbands, vertreten lassen. Am 23. August 2008 wurde die B-Probe beim A._ Laboratory unter der Aufsicht der Chemikerin Dr. E._ sowie des Chemikers F._ untersucht, während Dr. D._ als Zeuge und Vertreter des Beschwerdeführers anwesend war. Der Zeuge Dr. D._ bestätigte schriftlich, dass der Behälter mit der B-Urinprobe keine Anzeichen einer Fremdeinwirkung aufwies und die Identifikationsnummern auf der zu analysierenden Probe mit derjenigen auf der Probedokumentation übereinstimmte. Er bezeugte ausserdem, dass er bei der Öffnung der Probe dabei war. Die Analyse der B-Probe bestätigte den Nachweis von Capsaicin. Am 27. August 2008 wurden dem Beschwerdeführer die Resultate der B-Probe mitgeteilt. Am 26. September 2008 fand am Sitz der Beschwerdegegnerin in Lausanne ein Final Hearing statt. Die Parteien einigten sich darauf, dass am 8. November 2008 ein weiteres Hearing anzusetzen sei, damit zusätzliche Beweismittel vorgetragen und insbesondere die Sachverständigen befragt und ins Kreuzverhör genommen werden könnten. B. B.a Mit Entscheid des FEI-Tribunals vom 22. Dezember 2008 wurden das Pferd Y._ sowie der Beschwerdeführer für die Olympischen Spiele in Peking disqualifiziert und sämtliche Medaillen und Preisgelder aberkennt. Im Weiteren ordnete das FEI-Tribunal die Neuberechnung der Resultate des Springreiterteams Z._ unter Ausblendung der Resultate des Beschwerdeführers an. Schliesslich verhängte es gegen den Beschwerdeführer weitere Sanktionen, so insbesondere eine Wettkampfsperre von viereinhalb Monaten ab dem 21. August 2008 sowie eine Busse von Fr. 3'000.--. B.b Mit Appeal vom 19. Januar 2009 focht der Beschwerdeführer den Entscheid des FEI-Tribunals vom 22. Dezember 2008 beim Tribunal Arbitral du Sport (TAS) an und beantragte die Aufhebung dieses Entscheids. Mit Schiedsentscheid vom 4. Dezember 2009 wies das TAS den Appeal des Beschwerdeführers ab und bestätigte den angefochtenen Entscheid. Das TAS ging aufgrund der positiven Urinproben von einem Regelverstoss aus. Die verschiedenen Einwände des Beschwerdeführers erachtete das TAS als nicht stichhaltig, so insbesondere die Behauptung, die Urinproben seien kontaminiert gewesen, weil die mit der Entnahme der Urinprobe betraute Person keine Handschuhe getragen hätte, wie dies vorgeschrieben sei. Auch die vom Beschwerdeführer erst nach dem Final Hearing vorgebrachte These, die erwähnte Person habe zwar Handschuhe getragen, diese seien jedoch vermutlich bereits verunreinigt gewesen, erachtete das TAS als haltlos. Ausserdem schloss das TAS die Möglichkeit einer Verunreinigung der Urinprobe auch aufgrund einer weiteren Untersuchung der ersten Urinprobe hinsichtlich der Zusammensetzung der nachgewiesenen Substanz aus. C. Mit Beschwerde vom 19. Januar 2010 beantragt der Beschwerdeführer dem Bundesgericht, es seien das Urteil des TAS vom 4. Dezember 2009 und der Entscheid des FEI-Tribunals vom 22. Dezember 2008 aufzuheben. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat sich in einer kurzen Eingabe lediglich zur Frage ihrer Zuständigkeit geäussert, ansonsten jedoch auf eine Vernehmlassung verzichtet. Der Beschwerdeführer hat dem Bundesgericht eine Replik, die Beschwerdegegnerin eine Duplik eingereicht. D. Mit Verfügung vom 2. Februar 2010 wies das Bundesgericht die Gesuche des Beschwerdeführers um Gewährung der aufschiebenden Wirkung und um Anordnung vorsorglicher Massnahmen gegenüber der Beschwerdegegnerin ab.