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.