Sachverhalt:
A. A.a X._ (Beschwerdeführer) ist ein Fussballclub mit Sitz in Z._. Er gehört dem Fussballverband von Q._ an, der wiederum Mitglied der Fédération Internationale de Football Association (FIFA) mit Sitz in Zürich ist.
Y._ Sàrl (Beschwerdegegnerin) ist eine Fussballagentur mit Sitz in R._.
A.b Am 19. Februar 2003 schloss der Beschwerdeführer mit der Beschwerdegegnerin eine Vereinbarung betreffend den Transfer des Spielers A._ ab. Nach dieser Vereinbarung sollen die Parteien die Transfergebühr für einen zukünftigen Transfer des Spielers A._ zu einem ausländischen Club gemeinsam tragen.
Ziffer 4 dieser Vereinbarung sieht (nach der unbestrittenen englischen Übersetzung) Folgendes vor:
"The competent instance in case of a dispute concerning this Agreeement is the FIFA Commission, or the UEFA Commission, which will have to decide the dispute that could arise between the club and the agent".
Im Zusammenhang mit dem Transfer von A._ sowie zwei weiteren Fussballspielern kam es in der Folge zu Meinungsverschiedenheiten zwischen den Parteien hinsichtlich der geschuldeten Transfergebühren.
B. B.a Am 10. September 2008 leitete die Beschwerdegegnerin gestützt auf Ziffer 4 der Vereinbarung vom 19. Februar 2003 beim FIFA Players' Status Committee (Kommission für den Status von Spielern) ein Schiedsverfahren ein mit dem Rechtsbegehren, der Beschwerdeführer sei zur Zahlung von EUR 534'186.-- sowie USD 100'000.-- zu verurteilen.
Mit Schreiben vom 10. Dezember 2008 erklärte sich das FIFA Players' Status Committee gestützt auf Artikel 6.1 ihrer Verfahrensordnung für unzuständig, da es sich bei der klagenden Agentur um eine Gesellschaft und nicht um eine natürliche Person handle. Nachdem die Beschwerdegegnerin diesen Entscheid in Frage gestellt hatte, hielt die FIFA mit Schreiben vom 15. Januar 2009 an der Unzuständigkeit ihres Players' Status Committee fest.
B.b Am 25. Februar 2009 ersuchte die Beschwerdegegnerin das Obergericht des Kantons Zürich um die Benennung eines Schiedsrichters. Mit Entscheid vom 20. Oktober 2009 erwog das Obergericht des Kantons Zürich, es bestünden genügend Anhaltspunkte für das Bestehen einer Schiedsklausel und es sei dem Beschwerdeführer nicht gelungen, den summarischen Gegenbeweis für das Nichtbestehen einer Schiedsklausel zu erbringen, woraufhin es Urs Scherrer als Einzelschiedsrichter ernannte.
B.c Mit Schiedsentscheid vom 13. April 2010 erklärte sich der Einzelschiedsrichter für unzuständig. Er erwog, die Parteien seien sich offensichtlich einig, dass der bestehende Rechtsstreit einem auf Sportrecht spezialisierten Schiedsgericht unterbreitet werden soll, wobei der Beschwerdeführer sogar davon ausgehe, dass der Streit einem nach den Regeln einer Sportschiedsorganisation besetzten Sportschiedsgericht zu unterbreiten sei. Entsprechend erachtete es der Einzelschiedsrichter für nicht gerechtfertigt, die Schiedsklausel unwirksam werden zu lassen; allerdings ergebe sich daraus weder direkt noch mittelbar der Wille der Parteien, ihren Rechtsstreit einem Einzelschiedsrichter zu unterbreiten, weshalb er sich für unzuständig erklärte.
Die Beschwerdegegnerin focht den Entscheid des Einzelschiedsrichters vom 13. April 2010 beim Bundesgericht mit Beschwerde in Zivilsachen an (Verfahren 4A_280/2010). Das Verfahren wurde in der Folge bis zum Entscheid im vorliegend zu beurteilenden Beschwerdeverfahren sistiert.
B.d Am 14. Mai 2010 erhob die Beschwerdegegnerin beim Tribunal Arbitral du Sport (TAS) Schiedsklage gegen den Beschwerdeführer, im Wesentlichen mit den Rechtsbegehren, es sei der Beschwerdeführer zur Zahlung von USD 100'000.-- zuzüglich Zins zu 6 % seit dem 9. Februar 2006 sowie von EUR 534'186.-- zuzüglich Zins zu 8 % seit dem 1. Februar 2008 zu verurteilen. Der Beschwerdeführer bestritt die Zuständigkeit des TAS.
Mit Zwischenentscheid vom 17. März 2011 erklärte sich das TAS gestützt auf die in der Vereinbarung vom 19. Februar 2003 enthaltene Schiedsklausel für zuständig, über den zwischen den Parteien bestehenden Rechtsstreit im Zusammenhang mit dem Transfer des Fussballspielers A._ zu entscheiden (Dispositiv-Ziffer 1). Gleichzeitig erachtete sich das Schiedsgericht hinsichtlich der weiteren von der Beschwerdegegnerin eingeklagten Ansprüche für unzuständig (Dispositiv-Ziffer 2). Weiter regelte es die Verfahrens- und Parteikosten (Dispositiv-Ziffern 3 und 4).
C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es seien Dispositiv-Ziffern 1, 3 und 4 des Zwischenentscheids des TAS vom 17. März 2011 aufzuheben und es sei festzustellen, dass das TAS nicht zuständig sei.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Das Schiedsgericht hat auf eine Stellungnahme verzichtet.
Der Beschwerdeführer hat dem Bundesgericht eine Replik, die Beschwerdegegnerin eine Duplik eingereicht.
Erwägungen:
1. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (Art. 77 Abs. 1 lit. a BGG).
1.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Sowohl der Beschwerdeführer als auch die Beschwerdegegnerin hatten im massgebenden Zeitpunkt ihren Wohnsitz bzw. 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).
1.2 Die Beschwerde in Zivilsachen im Sinne von Art. 77 Abs. 1 BGG ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. Art. 77 Abs. 2 BGG, der die Anwendbarkeit von Art. 107 Abs. 2 BGG 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 (BGE 136 III 605 E. 3.3.4 S. 616 mit Hinweisen). Der Antrag des Beschwerdeführers ist insofern zulässig.
2. Der Beschwerdeführer macht geltend, die Vorinstanz habe sich zu Unrecht für zuständig erklärt (Art. 190 Abs. 2 lit. b IPRG).
2.1 Das Schiedsgericht prüfte gestützt auf Art. 178 Abs. 2 IPRG, ob die Parteien nach schweizerischem Recht eine gültige Schiedsklausel abgeschlossen haben. Nach Art. 1 Abs. 1 sowie Art. 2 Abs. 1 OR komme ein Vertrag zustande, wenn sich die Parteien über alle wesentlichen Punkte geeinigt hätten. Zu den objektiv wesentlichen Punkten einer Schiedsvereinbarung gehörten einerseits die Absicht der Parteien, ihren Rechtsstreit einem Schiedsgericht zur verbindlichen Entscheidung zu unterbreiten, und andererseits die Bestimmung des Streitgegenstands, der den Schiedsrichtern unterbreitet werden soll. Weitere Punkte, wie der Sitz des Schiedsgerichts, die Regeln hinsichtlich der Zusammensetzung des Schiedsgerichts, die Bezeichnung einer Schiedsorganisation, die Wahl der Verfahrenssprache sowie die Bestimmung der anwendbaren Verfahrensregeln gehörten nicht zu den wesentlichen Vertragspunkten, es sei denn, eine Partei habe diese - für die Gegenpartei erkennbar - als conditio sine qua non für den Abschluss der Vereinbarung angesehen. Ergebe die Auslegung der Schiedsvereinbarung, dass die Parteien ihren Rechtsstreit einem Schiedsgericht unterbreiten wollten, dass jedoch hinsichtlich des Ablaufs des Schiedsverfahrens keine Einigkeit bestehe, sei grundsätzlich nach einem Vertragsverständnis zu suchen, das die Gültigkeit der Schiedsklausel begünstige.
Aus dem Wortlaut von Ziffer 4 der Vereinbarung vom 19. Februar 2003 ergebe sich klar der Wille der Parteien, die staatliche Gerichtsbarkeit auszuschliessen und allfällige Streitigkeiten stattdessen in einem Schiedsverfahren entscheiden zu lassen. Die Parteien hätten zunächst eine Organisation bezeichnet, nämlich die FIFA oder die UEFA, die über einen Rechtsstreit entscheiden solle. Indem sie vorgesehen hätten, dass eine FIFA- oder UEFA-Kommission einen allfälligen Rechtsstreit im Zusammenhang mit ihrer Vereinbarung zu entscheiden habe, hätten sich die Parteien klar auf eine Institution geeinigt, die kein staatliches Gericht und nicht in einem der Staaten der Parteien ansässig, jedoch mit dem möglichen Streitgegenstand besonders vertraut sei. Eine Auslegung von Ziffer 4 nach dem Vertrauensprinzip ergebe, dass die Parteien Streitigkeiten aus der Vereinbarung einem Schiedsgericht unterbreiten wollten. Ausser in aussergewöhnlichen Fällen sei die Bezeichnung einer Schiedsinstitution oder eines Schiedsorgans als für die Parteien nicht subjektiv wesentlich zu erachten. Es bestünden keine Hinweise darauf, dass der Beschwerdeführer die in der Schiedsklausel bezeichnete Institution als derart wichtig angesehen hätte, dass er sich nicht für die Schiedsgerichtsbarkeit entschieden hätte, wäre ihm die Weigerung der FIFA, über den Rechtsstreit zu befinden, bekannt gewesen. Einen zusätzlichen Hinweise dafür, dass die in Ziffer 4 erwähnte "FIFA Commission" kein wesentlicher Punkt gewesen sei, sah das TAS darin, dass die Klausel neben der Zuständigkeit der FIFA alternativ auch diejenige der UEFA vorsehe. Dies sei ein wesentliches Indiz für den Umstand, dass die Parteien eine auf Sport spezialisierte Institution wollten, die mit Spielertransfers betreffenden Streitigkeiten vertraut ist, dass sie jedoch nicht auf eine einzelne Organisation fixiert waren. Zudem sei zu berücksichtigen, dass die FIFA-Statuten eine generelle Anfechtungsmöglichkeit des Entscheids der FIFA-Kommission für den Status von Spielern beim TAS vorsähen. Hätte es die FIFA-Kommission demnach nicht abgelehnt, über den zwischen den Parteien entstandenen Rechtsstreit zu entscheiden, wäre das TAS demnach - auf Berufung hin - zuständig gewesen.
Aus diesen Gründen sei von der Gültigkeit der abgeschlossenen Schiedsklausel auszugehen. Diese sei jedoch unklar und müsse hinsichtlich des konkret zuständigen Schiedsgerichts ausgelegt bzw. ergänzt werden. Dabei sei davon auszugehen, dass die Parteien ein Schiedsgericht mit mehreren Schiedsrichtern mit dem Entscheid über ihren Rechtsstreit betrauen wollten. Die Parteien hätten den Rechtsstreit eindeutig einem Schiedsgericht mit Sitz in der Schweiz unterbreiten wollen, wobei sie mit den beiden Alternativen FIFA (mit Sitz in Zürich) und UEFA (mit Sitz in Nyon VD) den konkreten Sitz offenliessen. Eine Zuständigkeit des TAS, das seinen Sitz in Lausanne - und damit ebenfalls im Kanton Waadt - habe, entspreche demnach der Wahl des Sitzes gemäss der abgeschlossenen Schiedsklausel. Die weitere Auslegung der Klausel ergebe, dass die Parteien beabsichtigten, eine auf Sportrecht (insbesondere im Bereich des Fussballs) spezialisierte Institution entscheiden zu lassen. Diesbezüglich sei allgemein bekannt, dass das TAS seit dem Jahr 2003 zur Beurteilung von Berufungen gegen Entscheide der FIFA zuständig sei. Das TAS habe daher eine reichhaltige Rechtsprechung im Bereich des Fussballs entwickeln können, insbesondere was die Regeln der FIFA angehe. Aus diesen Gründen sei das TAS am besten geeignet, über den Rechtsstreit zwischen den Parteien zu befinden, nachdem sich die FIFA für unzuständig erklärt und auch der Beschwerdeführer nicht vorgebracht habe, die UEFA würde tatsächlich darüber entscheiden. Entsprechend bejahte das TAS gestützt auf Ziffer 4 der Vereinbarung vom 19. Februar 2003 seine Zuständigkeit hinsichtlich der von der Beschwerdegegnerin eingeklagten Ansprüche im Zusammenhang mit dem Transfer des Spielers A._.
Aus diesen Gründen sei von der Gültigkeit der abgeschlossenen Schiedsklausel auszugehen. Diese sei jedoch unklar und müsse hinsichtlich des konkret zuständigen Schiedsgerichts ausgelegt bzw. ergänzt werden. Dabei sei davon auszugehen, dass die Parteien ein Schiedsgericht mit mehreren Schiedsrichtern mit dem Entscheid über ihren Rechtsstreit betrauen wollten. Die Parteien hätten den Rechtsstreit eindeutig einem Schiedsgericht mit Sitz in der Schweiz unterbreiten wollen, wobei sie mit den beiden Alternativen FIFA (mit Sitz in Zürich) und UEFA (mit Sitz in Nyon VD) den konkreten Sitz offenliessen. Eine Zuständigkeit des TAS, das seinen Sitz in Lausanne - und damit ebenfalls im Kanton Waadt - habe, entspreche demnach der Wahl des Sitzes gemäss der abgeschlossenen Schiedsklausel. Die weitere Auslegung der Klausel ergebe, dass die Parteien beabsichtigten, eine auf Sportrecht (insbesondere im Bereich des Fussballs) spezialisierte Institution entscheiden zu lassen. Diesbezüglich sei allgemein bekannt, dass das TAS seit dem Jahr 2003 zur Beurteilung von Berufungen gegen Entscheide der FIFA zuständig sei. Das TAS habe daher eine reichhaltige Rechtsprechung im Bereich des Fussballs entwickeln können, insbesondere was die Regeln der FIFA angehe. Aus diesen Gründen sei das TAS am besten geeignet, über den Rechtsstreit zwischen den Parteien zu befinden, nachdem sich die FIFA für unzuständig erklärt und auch der Beschwerdeführer nicht vorgebracht habe, die UEFA würde tatsächlich darüber entscheiden. Entsprechend bejahte das TAS gestützt auf Ziffer 4 der Vereinbarung vom 19. Februar 2003 seine Zuständigkeit hinsichtlich der von der Beschwerdegegnerin eingeklagten Ansprüche im Zusammenhang mit dem Transfer des Spielers A._.
2.2 2.2.1 Das Bundesgericht prüft die Zuständigkeitsrüge nach Art. 190 Abs. 2 lit. b IPRG 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 Art. 190 Abs. 2 IPRG vorgebracht oder ausnahmsweise Noven berücksichtigt werden (BGE 134 III 565 E. 3.1 S. 567; 133 III 139 E. 5 S. 141; 129 III 727 E. 5.2.2 S. 733).
2.2.2 Die Schiedsvereinbarung hat den Anforderungen von Art. 178 IPRG zu genügen. Hinsichtlich des Formerfordernisses (Art. 178 Abs. 1 IPRG) prüft das Bundesgericht in Sportangelegenheiten die Vereinbarung der Parteien darüber, ein Schiedsgericht anzurufen, mit einem gewissen "Wohlwollen"; dies mit dem Ziel, die rasche Streiterledigung durch spezialisierte Gerichte zu fördern, die wie das TAS hinreichende Gewähr für Unabhängigkeit und Unparteilichkeit bieten (BGE 133 III 235 E. 4.3.2.3 S. 244 f. mit Hinweisen). Die Grosszügigkeit, die in diesem Bereich die bundesgerichtliche Rechtsprechung prägt, zeigt sich namentlich in der Beurteilung der Wirksamkeit von Schiedsklauseln mittels Verweisungen (Urteile 4A_460/2010 vom 18. April 2011 E. 3.2.2; 4A_548/2009 vom 20. Januar 2010 E. 4.1; 4A_460/2008 vom 9. Januar 2009 E. 6.2 mit Hinweisen).
Die Gültigkeit einer Schiedsvereinbarung beurteilt sich gemäss Art. 178 Abs. 2 IPRG in inhaltlicher Hinsicht nach dem von den Parteien gewählten, dem auf die Streitsache, insbesondere dem auf den Hauptvertrag anwendbaren oder dem schweizerischen Recht. Keine der Parteien stellte sich im schiedsgerichtlichen Verfahren auf den Standpunkt, es müsse in Bezug auf die Gültigkeit der Schiedsklausel zunächst das auf die Vereinbarung vom 19. Februar 2003 anwendbare Recht eruiert werden; insbesondere berief sich die Beschwerdegegnerin nicht darauf, dieses sei hinsichtlich der materiellen Gültigkeit der Schiedsklausel vorteilhafter als das schweizerische Recht. Das TAS prüfte das Zustandekommen der fraglichen Schiedsvereinbarung - was auch vor Bundesgericht von keiner Partei in Frage gestellt wird - in Anwendung von Art. 178 Abs. 2 IPRG nach schweizerischem Recht.
2.2.3 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 (BGE 130 III 66 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 (BGE 129 III 675 E. 2.3 S. 679 f.). Das zur Entscheidung berufene Schiedsgericht muss entweder bestimmt oder jedenfalls bestimmbar sein. Die Bestellung des Schiedsgerichts kann nach einer von den Parteien gewählten Regelung (Art. 179 Abs. 1 IPRG) oder durch Entscheid des Gerichts am Sitz des Schiedsgerichts (Art. 179 Abs. 2 IPRG) erfolgen (BGE 130 III 66 E. 3.1 S. 70 f.; 129 III 675 E. 2.3 S. 680).
Bestimmungen in Schiedsvereinbarungen, die unvollständig, unklar oder widersprüchlich sind, gelten als pathologische Klauseln. Sofern sie nicht zwingende Elemente der Schiedsvereinbarung zum Gegenstand haben, namentlich die verbindliche Unterstellung der Streitentscheidung unter ein privates Schiedsgericht, führen sie nicht ohne Weiteres zu deren Ungültigkeit. Vielmehr ist vorerst durch Auslegung und allenfalls Vertragsergänzung in Anlehnung an das allgemeine Vertragsrecht nach einer Lösung zu suchen, die den grundsätzlichen Willen der Parteien respektiert, sich einer Schiedsgerichtsbarkeit zu unterstellen (BGE 130 III 66 E. 3.1 S. 71).
Steht 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 (BGE 130 III 66 E. 3.2 S. 71; 129 III 675 E. 2.3 S. 680). Steht 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. Eine unpräzise oder fehlerhafte Bezeichnung des Schiedsgerichts führt daher nicht zwingend zur Ungültigkeit der Schiedsvereinbarung (BGE 130 III 66 E. 3.2 S. 71 f.; 129 III 675 E. 2.3 S. 681).
Steht 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 (BGE 130 III 66 E. 3.2 S. 71; 129 III 675 E. 2.3 S. 680). Steht 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. Eine unpräzise oder fehlerhafte Bezeichnung des Schiedsgerichts führt daher nicht zwingend zur Ungültigkeit der Schiedsvereinbarung (BGE 130 III 66 E. 3.2 S. 71 f.; 129 III 675 E. 2.3 S. 681).
2.3 2.3.1 Der Beschwerdeführer bestreitet zunächst das Zustandekommen einer Schiedsvereinbarung. Dabei stellt er zu Unrecht in Abrede, dass die in der fraglichen Vertragsklausel enthaltene Willensäusserung nach Treu und Glauben so auszulegen ist, dass die Parteien allfällige Streitigkeiten aus ihrem Vertragsverhältnis durch Kommissionen der Fussballverbände FIFA oder UEFA entscheiden lassen wollten, anstatt diese den jeweiligen staatlichen Gerichten zu unterbreiten. Der Beschwerdeführer beanstandet lediglich in allgemeiner Weise, der vom TAS festgestellte Verzicht auf die staatliche Gerichtsbarkeit verstosse gegen den in der bundesgerichtlichen Rechtsprechung anerkannten Grundsatz, wonach ein solcher Verzicht nicht leichthin angenommen werden könne, sondern im Zweifelsfall eine restriktive Auslegung geboten sei (vgl. BGE 129 III 675 E. 2.3 S. 680 f.). Er legt jedoch nicht dar, inwiefern die Vertragsklausel dahingehend zu verstehen wäre, dass die staatliche Gerichtsbarkeit aufrechterhalten werde, bringt er doch selbst vor, nach Ziffer 4 der Vereinbarung solle "die jeweilige Kommission der Fussballverbände der FIFA oder UEFA zur Streitbeilegung kompetent sein" und erblickt er darin an anderer Stelle ebenfalls den eindeutigen Willen der Parteien, "ihre Streitigkeit einer ... Schiedsinstitution, namentlich derjenigen der FIFA-Kommission zu unterbreiten".
Ziffer 4 spricht zwar nicht ausdrücklich von "Schiedsgerichtsbarkeit", "Schiedsgericht", "Schiedsrichter", "Schiedsklausel" oder dergleichen (vgl. WERNER WENGER/CHRISTOPH MÜLLER, in: Basler Kommentar, Internationales Privatrecht, 2. Aufl. 2007, N. 32 zu Art. 178 IPRG), erklärt jedoch alternativ zwei internationale Fussballverbände für zuständig, im Falle einer Streitigkeit aus dem Vertrag zu entscheiden. Entgegen dem, was der Beschwerdeführer vorzubringen scheint, kann die Wortwahl "competent instance" sowie "decide the dispute" nicht so verstanden werden, dass die zwei erwähnten privaten Sportorganisationen, die beide mit der Welt des professionellen Fussballs vertraut sind, bei allfälligen Streitigkeiten aus dem Vertrag bloss vermitteln oder beraten sollen. Vielmehr ist nach Treu und Glauben davon auszugehen, dass der Beschwerdeführer als international bekannter Fussballclub und die Beschwerdegegnerin als Vermittlerin professioneller Fussballspieler einen allfälligen Rechtsstreit aus ihrem Transfervertrag verbindlich durch einen der beiden internationalen Fussballverbände entscheiden lassen wollten, ohne sich gleichzeitig den Gang an die staatlichen Gerichte in ihren jeweiligen Sitzstaaten offenzuhalten. Der Beschwerdeführer geht im Übrigen selbst davon aus, dass ein Entscheid der FIFA-Kommission für den Status von Spielern mit Berufung beim TAS hätte angefochten werden können. Unter diesen Umständen ist hinsichtlich des Verzichts auf die staatliche Gerichtsbarkeit nicht von einem Zweifelsfall auszugehen, der eine restriktive Auslegung gebieten würde.
Die Rüge des Beschwerdeführers, eine Auslegung der Willenserklärungen der Parteien nach dem Vertrauensprinzip führe nicht zu einem Ausschluss der staatlichen Gerichtsbarkeit, ist unbegründet. Das TAS ist ohne Verletzung von Bundesrecht vom Zustandekommen einer Schiedsvereinbarung ausgegangen.
2.3.2 Der Beschwerdeführer bringt weiter vor, die Bezeichnung der zuständigen "Kommission der UEFA" sei offensichtlich fehlerhaft, denn es sei allgemein bekannt, dass sich kein Organ der UEFA Streitigkeiten zwischen Spielervermittlern und Fussballclubs annehme. Entsprechende Streitigkeiten fielen ausschliesslich in den Kompetenzbereich der FIFA-Kommission für den Status von Spielern, die sich im konkreten Fall jedoch als nicht zuständig erklärte, da sie praxisgemäss nur Streitigkeiten zwischen Spielervermittlern und Fussballclubs entscheidet, wenn es sich beim Spielervermittler um eine natürliche Person handelt. Nachdem sich die erwähnte FIFA-Kommission der Streitigkeit nicht angenommen habe, so der Beschwerdeführer, sei die Schiedsklausel als erloschen bzw. anfänglich unmöglich zu betrachten.
Der Beschwerdeführer weist zwar zutreffend darauf hin, dass sich die Bezeichnung der beiden Kommissionen der FIFA bzw. der UEFA als ursprünglich unmöglich (Art. 20 Abs. 1 OR) erwiesen haben, da beide Organisationen aufgrund ihrer internen Regeln auf die Klage nicht eintreten können. Daraus folgt jedoch nicht bereits die Nichtigkeit der abgeschlossenen Schiedsklausel; vielmehr hat das TAS zutreffend geprüft, ob die in Ziffer 4 der Vereinbarung vom 19. Februar 2003 bezeichneten Organe von derart entscheidender Bedeutung waren, dass sich die Parteien gegen die Schiedsgerichtsbarkeit entschieden hätten, falls ihnen bewusst gewesen wäre, dass diese über einen Rechtsstreit gar nicht würden entscheiden können (vgl. auch die in der Beschwerde erwähnten JEAN-FRANÇOIS POUDRET/SÉBASTIEN BESSON, Comparative law of international arbitration, 2. Aufl. 2007, Rz. 161, nach denen die Bezeichnung einer nicht existierenden Schiedsinstitution nicht in jedem Fall, sondern nur unter bestimmten Voraussetzungen, zur Nichtigkeit der Schiedsklausel führt). Damit hat es im Ergebnis geprüft, was die Parteien nach ihrem hypothetischen Willen (vgl. BGE 131 III 467 E. 1.2 S. 470) vereinbart hätten, wenn ihnen die Nichtigkeit des mangelhaften Teils schon bei Vertragsabschluss bewusst gewesen wäre (vgl. Art. 20 Abs. 2 OR).
Entgegen dem, was der Beschwerdeführer zu vertreten scheint, hat das TAS seine Folgerung, dass eine Schiedsvereinbarung auch dann abgeschlossen worden wäre, wenn den Parteien bewusst gewesen wäre, dass keines der bezeichneten Organe über einen Rechtsstreit aus dem Transfervertrag entscheiden würde, nicht einfach aus einer allgemeinen Prämisse abgeleitet. Vielmehr hat es unter Berücksichtigung der individuellen Verhältnisse auch konkrete Hinweise für diese Ansicht erkannt: So weise einerseits der Umstand der alternativen Anrufung zweier Fussballverbände darauf hin, dass die Parteien nicht auf eine bestimmte Institution fixiert waren, sondern in erster Linie ein Schiedsgericht vorsehen wollten, das mit Fragen des Transfers professioneller Fussballspieler vertraut ist. Zudem hat das TAS die Behauptung des Beschwerdeführers, er hätte keine Schiedsvereinbarung abgeschlossen, wenn ihm die Unzuständigkeit der FIFA-Kommission für den Status von Spielern bewusst gewesen wäre, auch mit dem überzeugenden Hinweis darauf entkräftet, dass ein Entscheid dieser FIFA-Kommission nach den massgebenden Regeln der FIFA noch beim TAS hätte angefochten werden können, wovon auch der Beschwerdeführer ausgeht. In der Tat leuchtet es nicht ein, dass die Parteien zwar einen Entscheid der FIFA-Kommission für den Status von Spielern mit anschliessender Berufungsmöglichkeit an das TAS vorsehen wollten, jedoch bei blosser Aussicht auf eine direkte Klagemöglichkeit beim TAS oder einem anderen Schiedsgericht auf die Zuständigkeit der jeweiligen nationalen Gerichte bestanden hätten. Inwiefern Letzteres zutreffen soll, legt auch der Beschwerdeführer nicht dar. Im Übrigen verkennt er, dass bei Zweifeln am Bestehen eines auf Ganznichtigkeit gerichteten hypothetischen Parteiwillens nach den Regeln des allgemeinen Vertragsrechts der Teilnichtigkeit der Vorzug zu geben ist (Urteil 4C.156/2006 vom 17. August 2006 E. 3.2).
Dem TAS ist keine Bundesrechtsverletzung vorzuwerfen, wenn es trotz nichtiger Bezeichnung der in Ziffer 4 der Vereinbarung vom 19. Februar 2003 erwähnten Institutionen von der Aufrechterhaltung der Schiedsklausel ausging.
2.3.3 Steht - wie im konkreten Fall - fest, dass die Vertragsparteien die staatliche Gerichtsbarkeit zugunsten eines Schiedsgerichts ausgeschlossen haben, ist entgegen der in der Beschwerde vertretenen Ansicht möglichst nach einer Lösung zu suchen, die den grundsätzlichen Willen der Parteien beachtet, sich einer Schiedsgerichtsbarkeit zu unterstellen (vgl. BGE 130 III 66 E. 3.2 S. 71 f.). Zu diesem Zweck ist neben der Auslegung auch eine Ergänzung des Vertrags denkbar (BGE 130 III 66 E. 3.1 S. 71; vgl. WENGER/MÜLLER, a.a.O., N. 53 f. zu Art. 178 IPRG).
Die Teilnichtigkeit (Art. 20 Abs. 2 OR) der abgeschlossenen Schiedsvereinbarung vom 19. Februar 2003 ist, soweit dies möglich ist, durch Vertragsergänzung aufgrund des hypothetischen Parteiwillens zu beheben (vgl. BGE 120 II 35 E. 4a S. 40 f.; 114 II 159 E. 2c S. 163; 107 II 216 E. 3a und b S. 318 f.). Es ist zu fragen, was die Parteien vereinbart hätten, wenn ihnen der Teilmangel schon bei Vertragsschluss bewusst gewesen wäre (vgl. zur Ermittlung des hypothetischen Parteiwillens BGE 107 II 216 E. 3a S. 218; Urteile 4C.156/2006 vom 17. August 2006 E. 3.3; 4C.9/1998 vom 14. Mai 1998 E. 4b).
Das TAS hat ohne Verletzung von Bundesrecht erwogen, die Parteien hätten ihren Streit einem Schiedsgericht mit Sitz in der Schweiz unterbreiten wollen, das sich im Bereich des Sportrechts besonders auskennt. Die Bezeichnung der FIFA sowie der UEFA weist darauf hin, dass die Parteien eine Sportorganisation über allfällige Streitigkeiten aus ihrem Transfervertrag entscheiden lassen wollten, die mit dem Transferwesen im internationalen Fussballgeschäft vertraut ist. Zu beachten ist insbesondere, dass das TAS Entscheidungen der FIFA betreffend Spielertransfers auf Berufung hin überprüfen kann, und der Beschwerdeführer selbst anerkennt, dass gegen einen Entscheid der FIFA-Kommission für den Status von Spielern - falls sie ihre Zuständigkeit im konkreten Fall bejaht hätte - ein Rechtsmittel an das TAS zulässig gewesen wäre. Aufgrund dieser Umstände ist davon auszugehen, dass die Parteien allfällige Streitigkeiten aus ihrem Transfervertrag vom 19. Februar 2003 unmittelbar der Schiedsgerichtsbarkeit des TAS unterstellt hätten, das sich regelmässig mit Transfers von Fussballspielern auseinandersetzt, wäre ihnen die Unzuständigkeit der in Ziffer 4 aufgeführten Institutionen bewusst gewesen.
Der Einwand des Beschwerdeführers, eine direkte Zuständigkeit des TAS sei für ihn mit einem Rechtsverlust verbunden, da diesfalls eine Anfechtungsmöglichkeit nach den einschlägigen FIFA-Regeln entfalle, verfängt nicht, ergibt sich der angeführte Nachteil doch unmittelbar aus der Unzuständigkeit der bezeichneten FIFA-Kommission. Er bestreitet im Übrigen lediglich in allgemeiner Weise die Zuständigkeit des TAS, zeigt jedoch nicht auf, inwiefern die Parteien in jedem Fall auf der Möglichkeit eines zweistufigen Verfahrens bestanden hätten. Ebenfalls nicht stichhaltig ist der Verweis in der Beschwerde auf zwei Entscheide des TAS, in denen jeweils ein Nichteintretensentscheid der FIFA geschützt worden ist, zumal in diesen Berufungsfällen über die Zuständigkeit der FIFA zu entscheiden war und nicht eine direkte Klage an das TAS zur Diskussion stand.
Das TAS hat sich demnach ohne Verletzung von Bundesrecht als zuständig erklärt, über den zwischen den Parteien bestehenden Rechtsstreit im Zusammenhang mit dem Transfer des Fussballspielers A._ zu entscheiden.
3. 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. 10'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 12'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 7. November 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann