Sachverhalt: A. A.a A._ (Beschwerdeführer) mit Wohnsitz in I._, Ukraine, ist ein professioneller Torhüter der Fussballmannschaft des FC X._. Die Union des Associations Européennes de Football (UEFA, Beschwerdegegnerin) ist ein Verein schweizerischen Rechts mit Sitz in Nyon. A.b Am 30. November 2011 nahmen Dopingkontrolleure der UEFA bei A._ eine unangemeldete Probe ("out-of-competition doping control") vor. Die Urinprobe wurde am 19. Dezember 2011 in einem Labor in Österreich analysiert, wobei der Wirkstoff Furosemid nachgewiesen wurde. Furosemid ist eine Substanz, die gemäss Ziffer S5 der Verbotsliste der World Anti-Doping Agency (WADA) in Verbindung mit Artikel 4 des Anti-Doping-Reglements der UEFA (Ausgabe 2011) sowohl während als auch ausserhalb des Wettkampfs verboten ist. Am 10. Januar 2012 wurden A._, der ukrainische Fussballverband und der FC X._ von der UEFA über den Laborbefund informiert. Gleichzeitig wurde der Spieler auf sein Recht hingewiesen, eine Analyse der B-Probe zu verlangen, und es wurde ihm Frist zu einer Erklärung für das positive Testergebnis angesetzt. Ebenfalls am 10. Januar 2012 entschied der Vorsitzende der Kontroll- und Disziplinarkommission (Control and Disciplinary Body) der UEFA, A._ vorläufig zu sperren. Am 11. Januar 2012 teilte A._ der UEFA mit, dass er auf eine Analyse der B-Probe verzichte und unterbreitete ihr seine Erklärung für das positive Testergebnis. Auf Aufforderung der UEFA hin reichte A._ eine Erklärung zusammen mit seinen Beweismitteln ein. Mit Entscheid vom 27. Januar 2012 sprach die Kontroll- und Disziplinarkommission der UEFA gestützt auf Artikel 18.01 des Anti-Doping-Reglements eine zweijährige Sperre gegen A._ aus. Auf Gesuch des Vorsitzenden der Kontroll- und Disziplinarkommission der UEFA wurde der Sperre am 8. Februar 2012 von der Fédération Internationale de Football Association (FIFA) weltweite Geltung verliehen. A.c A._ focht den Entscheid der Kontroll- und Disziplinarkommission vom 27. Januar 2012 bei der Berufungskommission der UEFA an. Nach Durchführung einer mündlichen Verhandlung wies die UEFA-Berufungskommission das Rechtsmittel mit Entscheid vom 16. März 2012 ab und bestätigte die verhängte Sanktion. B. Am 28. März 2012 erklärte A._ beim Tribunal Arbitral du Sport (TAS) Berufung gegen den Entscheid der UEFA-Berufungskommission vom 16. März 2012. Am 11. Mai 2012 fand in Lausanne eine mündliche Verhandlung statt, in deren Rahmen der Spieler und seine Ehefrau sowie zwei Direktoren von Anti-Doping-Labors angehört wurden. Mit Entscheid vom 18. Mai 2012 (ausgefertigt am 11. Juli 2012) wies das TAS die Berufung ab. Das Schiedsgericht erwog, es sei unbestritten, dass in der Urinprobe des Spielers Furosemid nachgewiesen werden konnte und dieser Wirkstoff eine sowohl während als auch ausserhalb des Wettkampfs verbotene Substanz sei. Nachdem A._ auf eine Analyse der B-Probe verzichtet habe, sei damit eine Anti-Doping-Regelverletzung nach Artikel 2.01 (a) nachgewiesen, die bei einem Erstvergehen nach Artikel 18.01 des Anti-Doping-Reglements der UEFA grundsätzlich eine zweijährige Spielsperre nach sich ziehe. Im Weiteren sei unbestritten, dass der Spieler über keine gültige Ausnahmegenehmigung für den Gebrauch der verbotenen Substanz zu therapeutischen Zwecken verfügt habe. Eine Aufhebung oder Herabsetzung der Spielsperre sei gemäss Artikel 19 des Anti-Doping-Reglements nur möglich, wenn der Spieler aufzeigen könne, wie die Substanz in seinen Organismus gelangt ist. Das TAS hielt dafür, es sei A._ nicht gelungen, einen entschuldbaren Grund für den Nachweis der verbotenen Substanz in seinem Körper als überwiegend wahrscheinlich erscheinen zu lassen; eine Aufhebung oder Herabsetzung der zweijährigen Spielsperre falle daher ausser Betracht. Entsprechend bestätigte das TAS die verhängte Sperre. C. Mit Beschwerde in Zivilsachen beantragt A._ dem Bundesgericht, es sei der Schiedsentscheid des TAS vom 18. Mai 2012 aufzuheben. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Schiedsgericht hat auf eine Vernehmlassung verzichtet. Der Beschwerdeführer hat dem Bundesgericht am 27. November 2012 eine Replik, die Beschwerdegegnerin am 14. Dezember 2012 eine Duplik eingereicht.