Faits:
A. A.a L'Union des Associations Européennes de Football (UEFA) est une association de droit suisse, inscrite au registre du commerce; son siège est à Nyon. Elle constitue l'une des six confédérations continentales de la Fédération Internationale de Football Association (FIFA). L'UEFA a pour but de traiter toutes les questions qui concernent le football européen. Elle organise des compétitions et tournois internationaux de football, dont l'UEFA Europa League (UEL), compétition ouverte aux équipes de football professionnelles du continent européen.
Olympique des Alpes SA (OLA) est un club de football professionnel, constitué sous la forme d'une société anonyme de droit suisse; son siège social est à Martigny-Combe. Ce club se présente usuellement sous le nom de "FC Sion". Il dispute le championnat suisse de première division ("Super League"). Il est membre de la "Swiss Football League" (SFL) et, partant, de l'Association Suisse de Football (ASF). Cette dernière est membre de l'UEFA.
A.b Le 15 février 2008, OLA conclut un contrat de travail avec un joueur égyptien lié jusqu'en 2010 à un club égyptien. Ce dernier cita le joueur et OLA devant la Chambre de Résolution des Litiges de la FIFA (CRL-FIFA) pour cause de rupture injustifiée de contrat, respectivement incitation à une telle rupture. Par décision du 16 avril 2009, la CRL-FIFA interdit à OLA, à titre de sanction, de recruter de nouveaux joueurs durant les deux périodes d'enregistrement suivant la notification de sa décision. OLA interjeta un recours auprès du Tribunal Arbitral du Sport (TAS), à Lausanne; ce dernier le déclara irrecevable. Par arrêt du 12 janvier 2011, le Tribunal fédéral rejeta dans la mesure de sa recevabilité le recours déposé par OLA contre l'arrêt d'irrecevabilité du TAS (cause 4A_392/2010).
A.c Le 9 mai 2011, Christian Constantin, président du conseil d'administration de OLA, signa au nom du club la formule d'inscription à l'UEL 2011/2012, sans faire de réserve.
Cette formule précise entre autres que le signataire s'engage à respecter les statuts, règlements, directives et décisions de l'UEFA, ainsi qu'à reconnaître la compétence du TAS telle que prévue dans les statuts de l'UEFA. L'art. 61 des statuts précise que le TAS est seul compétent, à l'exclusion de tout tribunal ordinaire ou de tout autre tribunal arbitral, pour traiter en tant que tribunal arbitral ordinaire des litiges entre l'UEFA et les associations, ligues, clubs, joueurs ou officiels ainsi que des litiges de dimension européenne entre associations, ligues, clubs, joueurs ou officiels. L'art. 62 des statuts prévoit que toute décision prise par un organe de l'UEFA peut être exclusivement contestée auprès du TAS en tant que tribunal arbitral d'appel, à l'exclusion de tout tribunal ordinaire ou de tout autre tribunal arbitral.
A.d Les 5 et 6 juillet 2011, OLA demanda à la SFL de qualifier six nouveaux joueurs. Se référant à la décision de la CRL-FIFA du 16 avril 2009, la SFL s'y refusa. OLA et les six joueurs saisirent le Tribunal de recours de la SFL, lequel rejeta le recours en date du 29 juillet 2011. Le 2 août 2011, OLA recourut au TAS contre cette décision et requit des mesures provisionnelles.
Le 3 août 2011, les six joueurs déposèrent une requête de mesures provisionnelles dirigée contre la SFL et la FIFA auprès du Tribunal des districts de Martigny et St-Maurice, au motif que la décision du Tribunal de recours de la SFL portait atteinte à leurs droits de la personnalité. Dans une décision rendue le jour même à titre superprovisionnel, le juge de district déclara que les six joueurs devaient être considérés, tant par la SFL que par la FIFA, comme qualifiés en tant que joueurs de OLA, que cette dernière pouvait valablement les faire jouer et qu'il était fait interdiction à la FIFA d'entraver la remise du certificat international de transfert, ce jusqu'à droit connu sur la requête de mesures provisionnelles.
Le 5 août 2011, se pliant à l'injonction du juge de district, la SFL avisa OLA qu'elle pouvait valablement faire jouer les six joueurs jusqu'à droit connu sur la requête de mesures provisionnelles. La FIFA fera de même ultérieurement. Le 5 août 2011 également, OLA retira la requête de mesures provisionnelles déposée trois jours plus tôt auprès du TAS.
A.e Le 8 août 2011, OLA soumit à l'UEFA sa liste de joueurs pour l'UEL 2011/2012; cinq des six nouveaux joueurs y figuraient. La liste fut confirmée par l'ASF et approuvée par l'administration de l'UEFA.
Les 18 et 25 août 2011, OLA joua deux parties de barrage de l'UEL 2011/2012 contre le club écossais de Celtic. Les parties furent jouées sous protêt de Celtic; ce dernier reprochait à OLA d'aligner des joueurs qui n'avaient pas le droit de jouer. La première partie se termina sur un score nul, la seconde sur une victoire de OLA.
Par décision du 2 septembre 2011, l'Instance de contrôle et de discipline de l'UEFA (ICD-UEFA) retint que les cinq nouveaux joueurs de OLA n'étaient pas qualifiés au vu des règles de la SFL et de la FIFA. Elle admit les protêts de Celtic et déclara que OLA avait perdu les deux matches par forfait. OLA était ainsi éliminée de l'UEL 2011/2012.
A.f Le 2 septembre 2011 également, le Tribunal des districts de Martigny et St-Maurice rejeta une requête de mesures provisionnelles que les nouveaux joueurs, invoquant une violation de leurs droits de la personnalité, avaient introduite le jour précédent contre l'UEFA, cette fois-ci. Les joueurs déposèrent une nouvelle requête le 5 septembre 2011; elle sera derechef rejetée quelques jours plus tard.
Le 6 septembre 2011, OLA requit des mesures provisionnelles contre l'UEFA devant le Tribunal cantonal valaisan, au motif que l'UEFA violait la législation suisse sur la concurrence. Le lendemain, le Tribunal cantonal déclara la requête irrecevable, pour défaut de compétence ratione loci.
A.g Le 9 septembre 2011, OLA requit des mesures provisionnelles contre l'UEFA devant le Tribunal cantonal vaudois. Elle soutenait qu'elle était victime d'une restriction illicite d'accès à la concurrence résultant de la décision de l'ICD-UEFA du 2 septembre 2011, laquelle constituait à son sens un abus de position dominante (cf. art. 7 al. 1 de la loi fédérale sur les cartels et autres restrictions à la concurrence [LCart; RS 251]).
Par ordonnance de mesures superprovisionnelles du 13 septembre 2011, le juge délégué de la Cour civile du Tribunal cantonal vaudois ordonna à l'UEFA d'admettre le club valaisan comme participant à l'UEL 2011/2012 et de prendre toutes mesures utiles aux fins de l'intégrer dans la compétition, ainsi que de considérer les six nouveaux joueurs comme qualifiés en tant que joueurs de OLA et de les admettre dans la compétition de l'UEL 2011/2012, jusqu'à droit connu sur le sort de la requête de mesures provisionnelles et sous la menace de la peine prévue à l'art. 292 CP. Par ordonnance de mesures provisionnelles du 5 octobre 2011, le juge délégué, après avoir tenu audience, confirma la décision rendue à titre superprovisoire, jusqu'à droit connu sur l'action au fond; en outre, il interdit à l'UEFA de prononcer un forfait au préjudice de OLA en raison de la participation des nouveaux joueurs, également jusqu'à droit connu au fond.
A.h Le 13 septembre 2011, l'Instance d'appel de l'UEFA rejeta le recours déposé par OLA contre la décision de l'ICD-UEFA du 2 septembre 2011, confirma les deux défaites par forfait de OLA contre Celtic et refusa de prononcer les mesures provisionnelles requises par le club valaisan. Par la suite, OLA contestera cette décision de l'Instance d'appel et ouvrira action contre l'UEFA pour violation des droits des sociétaires (art. 75 CC) devant le Tribunal d'arrondissement de Nyon.
B. Le 26 septembre 2011, l'UEFA adressa une requête d'arbitrage au TAS. Elle concluait à ce qu'il fût dit et prononcé que la réglementation de l'UEFA, en particulier celle relative à l'UEL 2011/2012, ainsi que les mesures disciplinaires prises par l'UEFA et ses organes à l'encontre de OLA n'étaient pas contraires au droit suisse des cartels et de la concurrence, que OLA n'était pas en droit d'être réintégrée dans la compétition de l'UEL 2011/2012, que l'UEFA n'avait pas violé le droit suisse ni les droits de la personnalité tant de OLA que des nouveaux joueurs du club, que ces joueurs n'étaient pas habilités à participer à l'UEL 2011/2012, que les mesures provisionnelles prises par le Tribunal cantonal vaudois étaient levées, que tout droit à demander des dommages-intérêts à l'UEFA était nié et que toute autre conclusion appropriée de l'UEFA était admise.
OLA conclut à ce que le TAS déclinât sa compétence et déclarât la requête de l'UEFA irrecevable.
Les quatre clubs de football Atlético de Madrid, Udinese, Celtic et Stade Rennais furent admis comme parties intervenantes. A ce titre, ils ne pouvaient pas prendre de conclusions propres, mais uniquement soutenir celles des parties principales.
Par sentence arbitrale du 31 janvier 2012, la Formation du TAS constituée pour connaître de la cause (ci-après: la Formation) admit d'abord sa compétence pour statuer par la voie de l'arbitrage ordinaire et rejeta l'exception d'incompétence soulevée par OLA. Sur le fond, elle admit partiellement la requête; elle confirma ainsi que OLA n'était pas en droit d'être réintégrée dans l'UEL 2011/2012 et leva les mesures provisionnelles prononcées le 5 octobre 2011 par le Tribunal cantonal vaudois. Pour le surplus, elle déclara irrecevables les conclusions au fond de l'UEFA: celles en constatation de la conformité des règles et décisions de l'UEFA avec le droit suisse des cartels et de la concurrence, faute d'intérêt légal; celles en constatation relatives à la violation des droits de la personnalité des joueurs de OLA, parce que ceux-ci n'étaient pas parties à la procédure; celles en constatation que ces joueurs étaient exclus de l'UEL 2011/2012, parce qu'elles portaient sur une question juridique abstraite; celles visant à nier tout droit à des dommages-intérêts contre l'UEFA, faute de motivation; celles relatives à d'éventuelles autres conclusions appropriées, faute de spécification. La Formation mit deux tiers des frais d'arbitrage à la charge de OLA; en outre, elle condamna le club valaisan à verser 40'000 fr. à l'UEFA pour ses dépens.
C. Par mémoire non daté remis à la poste le 7 mars 2012, OLA (ci-après: la recourante) interjette un recours en matière civile, concluant à l'annulation de la sentence arbitrale du 31 janvier 2012.
L'UEFA (ci-après: l'intimée) ainsi que les intervenants Udinese, Atlético de Madrid et Celtic concluent principalement à l'irrecevabilité du recours et subsidiairement à son rejet. L'intervenant Stade Rennais n'a pas pris position.
Invité à déposer des observations en qualité d'autorité précédente, le TAS, par son secrétaire général, a mandaté un avocat pour y donner suite; il confirme sa sentence et propose le rejet du recours.
La recourante s'est déterminée sur ces écritures.
Par la suite, l'intimée a encore fourni des observations.
Considérant en droit:
1. Les parties principales à la procédure arbitrale, à savoir l'intimée et la recourante, ont leur siège en Suisse, si bien que la procédure est un arbitrage interne (art. 353 al. 1 CPC; art. 176 al. 1 LDIP). Le fait que les parties intervenantes, non habilitées à prendre des conclusions propres, ont leur siège à l'étranger est sans pertinence à cet égard.
Pour l'arbitrage interne, le recours en matière civile est recevable aux conditions prévues aux art. 389 à 395 CPC (art. 77 al. 1 let. b LTF). Faute de déclaration expresse des parties principales prévoyant un recours devant le tribunal cantonal compétent en vertu de l'art. 356 al. 1 CPC (art. 390 al. 1 CPC), la sentence, contre laquelle aucune voie de recours arbitrale n'existe (art. 391 CPC), peut faire l'objet d'un recours devant le Tribunal fédéral (art. 389 al. 1 CPC). La procédure est régie par la LTF, sauf disposition contraire du CPC contenue aux art. 389 à 395 (art. 389 al. 2 CPC).
Sauf exception qui n'entre pas en ligne de compte en l'espèce (cf. art. 395 al. 4 CPC), le recours en matière civile dirigé contre une sentence arbitrale interne est de nature cassatoire (cf. art. 77 al. 2 LTF; art. 395 al. 1 CPC; arrêt 4A_424/2011 du 2 novembre 2011 consid. 1.2). La recourante l'a bien vu en concluant à l'annulation de la sentence attaquée et l'intimée erre lorsqu'elle prétend que ladite conclusion est irrecevable.
Le recours porte sur la constatation que la recourante n'est pas en droit d'être réintégrée dans l'UEL 2011/2012 et sur la levée des mesures provisionnelles prononcées le 5 octobre 2011 par le Tribunal cantonal vaudois, ainsi que sur la question accessoire des frais et dépens. La recourante n'est en revanche pas lésée par les points du dispositif déclarant irrecevables les autres conclusions de l'intimée.
2. Le Tribunal fédéral contrôle d'office et librement la recevabilité des recours qui lui sont soumis (ATF 137 III 417 consid. 1 et les arrêts cités), ce qui implique notamment d'examiner la qualité pour recourir.
2.1 Selon l'art. 76 al. 1 let. b LTF, le recourant doit notamment avoir un intérêt digne de protection à l'annulation de la décision attaquée. Cette exigence est identique à celle posée par l'art. 89 al. 1 let. c LTF pour le recours en matière de droit public (cf. Message du 28 juin 2006 relatif au code de procédure civile suisse, FF 2006 6890 ch. 5.3.2). L'intérêt digne de protection consiste dans l'utilité pratique que l'admission du recours apporterait à son auteur, en lui évitant de subir un préjudice de nature économique, idéale, matérielle ou autre que la décision attaquée lui occasionnerait (ATF 137 II 40 consid. 2.3 p. 43). L'intérêt doit être actuel, c'est-à-dire qu'il doit exister non seulement au moment du dépôt du recours, mais encore au moment où l'arrêt est rendu (ATF 137 I 296 consid. 4.2 p. 299; 137 II 40 consid. 2.1 p. 41). Le Tribunal fédéral déclare le recours irrecevable lorsque l'intérêt digne de protection fait défaut au moment du dépôt du recours. En revanche, si cet intérêt disparaît en cours de procédure, le recours devient sans objet (ATF 137 I 23 consid. 1.3.1 p. 24 s. et les arrêts cités). Il est dérogé exceptionnellement à l'exigence d'un intérêt actuel lorsque la contestation à la base de la décision attaquée est susceptible de se reproduire en tout temps dans des circonstances identiques ou analogues, que sa nature ne permet pas de la trancher avant qu'elle ne perde son actualité et que, en raison de sa portée de principe, il existe un intérêt public suffisamment important à la solution de la question litigieuse (ATF 137 I 23 consid. 1.3.1 p. 25; 136 II 101 consid. 1.1 p. 103; 135 I 79 consid. 1.1 p. 81).
2.2 Dans son mémoire de mars 2012, la recourante fait valoir que la compétition de l'UEL 2011/2012 est alors toujours en cours, tout en observant qu'en cas d'admission du recours, sa réintégration "semble difficile, sinon impossible". Elle voit néanmoins un intérêt au recours dans le fait qu'elle pourrait mettre en cause la régularité de la compétition et obtenir des dommages-intérêts si son exclusion se révélait injustifiée. Dans sa prise de position, le TAS émet de sérieux doutes sur l'intérêt actuel de la recourante à obtenir l'annulation de la sentence du 31 janvier 2012, alors que la recourante reconnaît elle-même qu'une réintégration dans la compétition semble difficile, sinon impossible en cas d'admission du recours. A cela, la recourante répond, dans ses observations de juin 2012, que si l'annulation de la sentence ne permet pas sa réintégration dans une compétition désormais achevée, c'est parce que le TAS a tardé à statuer et qu'en agissant de même à l'avenir, le TAS pourrait "échapper à toute sanction" chaque fois qu'une situation comparable se présenterait.
Devant le Tribunal fédéral, la querelle porte sur la confirmation que la recourante n'est pas en droit d'être réintégrée dans l'UEL 2011/2012 et sur la levée des mesures provisionnelles prononcées par le Tribunal cantonal vaudois.
Il est notoire que la compétition de l'UEL 2011/2012 est aujourd'hui terminée. Dans ces circonstances, on ne discerne pas l'intérêt de la recourante à obtenir l'annulation d'une sentence constatant qu'elle n'a pas le droit d'être réintégrée dans cette compétition et levant des mesures provisionnelles qui ordonnent qu'elle puisse y participer. Même si le défaut d'intérêt au recours était dû, comme la recourante le soutient, aux lenteurs du TAS à statuer, cela ne changerait rien au fait qu'il n'existe plus, à l'heure actuelle, d'intérêt à une décision au fond. L'intention de la recourante de demander ultérieurement réparation du dommage qui aurait été causé par son exclusion prétendument illicite de la compétition ne fonde pas, à elle seule, un intérêt digne de protection; la décision attaquée ne peut d'ailleurs pas lui être opposée dans une éventuelle procédure ultérieure en dommages-intérêts (ATF 126 I 144 consid. 2a p. 148; 125 I 394 consid. 4a p. 397). En outre, la recourante n'allègue pas - et rien ne permet de retenir - que la situation ayant conduit à son exclusion de l'UEL 2011/2012 soit susceptible de se répéter à l'avenir. Une dérogation à l'exigence de l'intérêt actuel ne se justifie donc pas.
Il s'ensuit que le recours est sans objet sur la question principale.
3. La sentence attaquée met des frais et dépens à la charge de la recourante. Cette dernière a certes un intérêt légitime et actuel à obtenir l'annulation de cette condamnation (cf. ATF 117 Ia 251 consid. 1b p. 255). Mais cela ne signifie pas qu'elle peut, par le biais d'une contestation de sa condamnation à des frais et dépens, faire examiner de manière indirecte des griefs sans objet ou irrecevables contre la décision au fond (cf. ATF 129 II 297 consid. 2.2 p. 300; 100 Ia 298 consid. 4 p. 299). Lorsqu'il ne peut pas être entré en matière sur les griefs soulevés contre la décision au fond, le recourant peut faire valoir uniquement que la décision sur les frais et dépens doit être annulée ou modifiée pour des motifs autres que ceux qu'il invoquait à propos de la question principale (cf. ATF 109 Ia 90; plus récemment, arrêt 4A_637/2010 du 2 février 2011 consid. 4).
En l'espèce, le recours ne contient pas de moyens spécifiques contre la décision sur les frais et dépens (cf. art. 393 let. f CPC), qui seraient différents de ceux articulés contre la décision au fond; les griefs contre la condamnation aux frais et dépens se confondent avec ceux contre la décision au fond. Le recours est dès lors irrecevable sur la question des frais et dépens (cf. art. 77 al. 3 LTF).
4. Sur le vu de ce qui précède, le recours est irrecevable dans la mesure où il n'est pas sans objet.
En règle générale, les frais judiciaires et les dépens de la partie qui a obtenu gain de cause sont mis à la charge de la partie qui succombe (art. 66 al. 1 et art. 68 al. 1 LTF). Dans la mesure où le recours est sans objet, il convient d'appliquer aux frais et dépens l'art. 72 PCF, par renvoi de l'art. 71 LTF. Le Tribunal fédéral statue alors par une décision sommairement motivée en tenant compte de l'état de choses existant avant le fait qui met fin au litige. Il se fonde en premier lieu sur l'issue probable qu'aurait eue la procédure. Si cette issue ne peut être déterminée dans le cas concret sans plus ample examen, les règles générales de la procédure civile s'appliquent: les frais et dépens seront mis à la charge de la partie qui a provoqué la procédure devenue sans objet ou chez laquelle sont intervenues les causes ayant conduit à ce que cette procédure devienne sans objet (cf. ATF 118 Ia 488 consid. 4a p. 494; plus récemment, arrêt 4A_636/2011 du 18 juin 2012 consid. 4).
En l'espèce, la recourante a provoqué la procédure déclarée sans objet et il n'apparaît pas sans autre que les griefs soulevés dans le recours étaient bien fondés. En conséquence, la recourante prendra à sa charge les frais de la procédure et versera des dépens à l'intimée ainsi qu'aux trois intervenants qui ont déposé de très brèves réponses.
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable dans la mesure où il n'est pas sans objet.
2. Les frais judiciaires, arrêtés à 15'000 fr., sont mis à la charge de la recourante.
3. La recourante versera, à titre de dépens, une indemnité de 17'000 fr. à l'intimée et une indemnité de 2'000 fr. à chacun des intervenants Atlético de Madrid SAD, Celtic PLC et Udinese Calcio SpA.
4. Le présent arrêt est communiqué aux mandataires des parties et au Tribunal Arbitral du Sport (TAS).
Lausanne, le 16 juillet 2012
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
La Greffière: Godat Zimmermann