Sachverhalt: A. A.a Die Internationale Eishockey-Föderation (International Ice Hockey Federation, IIHF, Beschwerdeführerin) ist ein im Handelsregister eingetragener Verein mit Sitz in Zürich. Zu ihren Mitgliedern zählt der Schweizerische Eishockeyverband (Swiss Ice Hockey Federation, SIHF), ebenfalls ein Verein mit Sitz in Zürich. In diesem nationalen Dachverband findet sich namentlich die Schweizerische Eishockey Nationalliga GmbH (NL-GmbH) mit Sitz in Ittigen BE. Die SCB Eishockey AG (SCB AG, Beschwerdegegnerin) ist eine Aktiengesellschaft mit Sitz in Bern. Ihr Zweck ist die Durchführung, Organisation und Leitung des professionellen Spielbetriebs einer Eishockeymannschaft (SCB, Schlittschuh Club Bern) inklusive Durchführung der Spiele und Abwicklung des Transferwesens. Sie ist Mitglied des SIHF und der NL-GmbH. A.b Im April 2008 hat die Beschwerdeführerin mit der SIHF und der NL-GmbH die Vereinbarung über die Teilnahme schweizerischer Klubs an der CHL (Champions Hockey League), einem europäischen Eishockey-Turnier auf hohem Niveau, abgeschlossen (CHL-Vereinbarung). Darin sind unter anderem Geldleistungen für einen Totalbetrag von EUR 10'000'000.-- an die teilnehmenden Klubs festgelegt (Art. 8) sowie die Regeln, nach welchen die Klubs zur Teilnahme berechtigt sind (Art. 10). Die CHL-Vereinbarung sieht vor, dass schweizerisches Recht anwendbar ist und dass allfällige Streitigkeiten zwischen den Parteien in Zusammenhang mit dem Inhalt der Vereinbarung ("any dispute between the parties under or relating to the subject matter of this Agreement") ausschliesslich und endgültig durch Schiedsspruch des Internationalen Sportgerichtshofs in Lausanne (Tribunal arbitral du sport, TAS) entschieden werden. Art. 10 der CHL-Vereinbarung ("Entries for the Competition") enthält namentlich folgende Bestimmungen: "10.1 European IIHF member national association / leagues shall enter a certain number of clubs for this competition (...). 10.3 (...) For the first season, national associations / leagues shall be represented on the following basis: (...) c) Switzerland (...) : One representative being the top league national champion (...). 10.4 Clubs must be entered by the National Association / League by means of the official entry form (...)." Mit Brief vom 19. Mai 2008 hat sich die Beschwerdegegnerin bei der Beschwerdeführerin um Teilnahme an der CHL 2008/2009 beworben. Das von ihr unterzeichnete Teilnahmeformular ("Entry Form") sieht namentlich vor, dass der Wettkampf nach den Regeln durchgeführt wird, die sich in den entsprechenden Vereinbarungen zwischen der Beschwerdeführerin und dem für den antragstellenden Klub zuständigen nationalen Verband sowie in den Regelwerken der Beschwerdeführerin finden, und dass der antragstellende Klub alle Verpflichtungen akzeptiert, die in diesen Vereinbarungen und Regelwerken stehen. Auf Grund ihrer Ergebnisse in der nationalen Meisterschaft erfüllte die Beschwerdegegnerin die Bedingungen, um 2009/10 und 2010/11 an der CHL teilzunehmen. A.c Im Januar 2009 stellte jenes Unternehmen, das die CHL finanziell unterstützte, seine Zahlungen infolge der Finanzkrise ein. Am 9. April 2009 löste die Beschwerdeführerin die Vereinbarung mit ihm auf und informierte verschiedene nationale Verbände, darunter die SIHF, dass sie nicht mehr in der Lage sei, die CHL 2009/10 und 2010/11 zu finanzieren und das Preisgeld von je EUR 10'000'000.-- zu garantieren. Mitte Juni beschloss die Beschwerdeführerin, mangels neuer Investoren die CHL für die Saison 2009/10 zu suspendieren. Ende 2009 schlossen dann die Beschwerdeführerin einerseits und die SIHF und NL-GmbH andererseits ein "Settlement Agreement" mit dem Ziel, die CHL in der Saison 2010/11 wieder aufzunehmen. B. B.a Mit Schiedsklage vom 13. Oktober 2010 beantragte die Beschwerdegegnerin dem TAS, es sei die Beschwerdeführerin zu verurteilen, ihr die Beträge von EUR 107'600.-- (später reduziert auf EUR 53'800.--), EUR 322'800.-- und Fr. 580'975.40 zu bezahlen, jeweils mit Verzugszinsen. Die beiden ersten Beträge entsprechen dem vermeintlichen Preisgeld, das die Beschwerdegegnerin auf Grund der CHL-Vereinbarung für die Teilnahme an der CHL in den beiden Saisons 2009/10 und 2010/11 auf jeden Fall erhalten hätte. Der dritte Betrag entspricht dem Schaden, den die Beschwerdegegnerin dadurch erlitten habe, dass sie im Hinblick auf die Teilnahme an der CHL in der Saison 2009/10 drei Spieler eingekauft hat. In ihrer Antwort vom 11. November 2010 schloss die Beschwerdeführerin hauptsächlich dahin, das TAS möge seine Zuständigkeit verneinen. Eventualiter schloss sie auf Abweisung der Klage. B.b Mit Zwischenentscheid ("Partial Award on Jurisdiction") vom 13. September 2011 bejahte das TAS seine Zuständigkeit. Die zentrale Erwägung lautet dahingehend, dass es sich bei Art. 10 der CHL-Vereinbarung, die bestimmt, welche Klubs auf Grund ihrer Leistungen in der nationalen Meisterschaft zur Teilnahme am CHL berechtigt sind, um einen echten Vertrag zu Gunsten Dritter (d.h. zu Gunsten der teilnahmeberechtigten Klubs) handle (Art. 112 Abs. 2 OR), und dass folglich auch die in der CHL-Vereinbarung enthaltene Schiedsklausel auf diese Dritte zur Anwendung gelange. C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin dem Bundesgericht, es sei der Zwischenentscheid vom 13. September 2011 aufzuheben und die Zuständigkeit des TAS zu verneinen. Die Beschwerdegegnerin schliesst in ihrer Vernehmlassung auf Abweisung der Beschwerde. Das TAS reichte Bemerkungen ein, die Parteien Replik und Duplik. Mit Präsidialverfügung vom 7. November 2011 wurde der Beschwerde die aufschiebende Wirkung erteilt.