Faits:
A. Du 16 août 1993 au 31 décembre 2002, B._, né en 1976, a travaillé au service de X._. A ce titre, il était assuré contre le risque d'accidents auprès de la Caisse nationale suisse d'assurance en cas d'accidents (CNA). Dès le 1er janvier 2003, le prénommé a été engagé par le Groupe Mutuel Assurances.
Le 16 janvier 1994, B._ a été renversé par une voiture alors qu'il circulait en vélomoteur. La CNA a pris en charge les conséquences de cet accident qui a occasionné une commotion cérébrale, ainsi que plusieurs fractures (de l'os temporal, de l'arc moyen de la 6ème côte et de la clavicule gauche). L'évolution a été favorable et le prénommé a pu reprendre son travail en plein dès le 14 mars 1994.
Le 22 avril 2010, le Groupe Mutuel Assurances a annoncé à la CNA une rechute de l'accident de 1994 sous la forme de luxations récidivantes de l'épaule gauche. Le dernier événement, lors duquel B._ s'était luxé l'épaule gauche en déplaçant des feuilles de papier, datait du 2 avril 2010. Dans un rapport médical LAA, le docteur M._ a fait état d'une instabilité de l'épaule gauche entraînant des luxations à répétitions. Au cours d'un entretien avec un inspecteur de la CNA le 6 juillet 2010, l'intéressé a indiqué qu'il n'avait pas eu de problèmes à l'épaule gauche depuis 1994 jusqu'à un événement survenu en 1998 ou 1999 en jouant au football. Il était entré en collision avec un autre joueur, ce qui avait provoqué une luxation de son épaule gauche qu'il avait réduite lui-même. A partir de cet incident, il avait présenté de nombreux autres épisodes de luxations. Le 10 août 2010, B._ a subi une opération de stabilisation de l'épaule gauche.
Par décision du 29 novembre 2010, la CNA a refusé de prendre en charge les troubles à l'épaule gauche. D'une part, il n'existait pas de corrélation probable entre ceux-ci et l'accident du 16 janvier 1994. D'autre part, il n'était pas établi avec suffisamment de vraisemblance qu'un autre accident engageant sa responsabilité soit à l'origine de l'atteinte en cause. L'assuré a formé opposition, en produisant un courrier daté du 14 mai 2002 de son médecin traitant de l'époque, dans lequel il était mentionné qu'il avait subi une luxation de l'épaule gauche en avril 2002. La CNA a écarté l'opposition dans une nouvelle décision du 9 février 2011.
B. B._, de même que l'assureur-maladie et l'assureur perte de gain de celui-ci (le Groupe Mutuel Assurances) ont déféré cette dernière décision à la Cour des assurances sociales du Tribunal cantonal valaisan.
La juridiction cantonale a admis les recours, annulé la décision attaquée, et condamné la CNA à prendre en charge la rechute des troubles à l'épaule gauche annoncée le 22 avril 2010 (jugement du 19 décembre 2011).
C. La CNA interjette un recours en matière de droit public contre ce jugement, dont elle requiert l'annulation. Elle conclut à la confirmation de sa décision sur opposition du 9 février 2011.
Le Groupe Mutuel Assurances conclut au rejet du recours. B._ et l'Office fédéral de la santé publique ont renoncé à se déterminer.

Considérant en droit:
1. Le recours est dirigé contre un arrêt final (<ref-law>) rendu en matière de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF). Il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi. Il est donc recevable.
2. Lorsque sont en jeu - comme ici - des prestations en espèces (indemnités journalières) et en nature de l'assurance-accidents (traitement médical), le Tribunal fédéral constate avec un plein pouvoir d'examen les faits communs aux deux objets litigieux et se fonde sur ces constatations pour statuer, en droit, sur ces deux objets. En revanche, les faits qui ne seraient pertinents que pour statuer sur le droit aux prestations en nature ne sont revus que dans les limites définies par les art. 97 al. 1 et 105 al. 2 LTF (SVR 2011 UV n° 1 p. 1, 8C_584/2009 consid. 4).
3. La juridiction cantonale a estimé qu'il était établi à satisfaction de droit que B._ avait été victime d'une luxation de l'épaule gauche pour la première fois consécutivement à un choc avec un autre joueur au cours d'un match de football, le 8 avril 2002. A ses yeux, en effet, les déclarations de B._ au sujet d'un accident de football ayant occasionné le premier déboitement de son épaule gauche n'avaient pas varié et apparaissaient vraisemblables. Par ailleurs, l'existence de l'atteinte était confirmée par le document du 14 mai 2002 du docteur W._. Le fait que ce médecin n'en ait pas précisé la cause ne suffisait pas à écarter les déclarations de l'assuré, pas plus qu'il n'était décisif que ce dernier avait dans un premier temps situé la date de l'accident en 1998 ou 1999.
En substance, la CNA fait valoir une mauvaise application par les premiers juges des principes applicables en matière de preuve. En tout état de cause, elle estime qu'il est nécessaire d'ordonner une instruction complémentaire sur la question de la causalité puisque seul le médecin traitant actuel de l'assuré, le docteur M._, s'était prononcé sur ce point. Il n'était en effet pas exclu, vu la fréquence des luxations subies par l'assuré, que l'atteinte était désormais exclusivement d'étiologie dégénérative.
4. 4.1 Dans le domaine des assurances sociales, la procédure est régie par le principe inquisitoire, d'après lequel les faits pertinents de la cause doivent être constatés d'office par le juge. Mais ce principe n'est pas absolu. Sa portée est restreinte par le devoir des parties de collaborer à l'instruction de l'affaire. Celui-ci comprend en particulier l'obligation des parties d'apporter, dans la mesure où cela peut être raisonnablement exigé d'elles, les preuves commandées par la nature du litige et des faits invoqués, faute de quoi elles risquent de devoir supporter les conséquences de l'absence de preuves (<ref-ruling> consid. 2 p. 195 et les références; cf. <ref-ruling> consid. 3.2 p. 183).
4.2 Par ailleurs, le juge des assurances sociales fonde sa décision, sauf dispositions contraires de la loi, sur les faits qui, faute d'être établis de manière irréfutable, apparaissent comme les plus vraisemblables, c'est-à-dire qui présentent un degré de vraisemblance prépondérante (<ref-ruling> consid. 5b p. 360; <ref-ruling> consid. 2 p. 195 et les références; cf. <ref-ruling> consid. 3.2 et 3.3 p. 324 s.). Il ne suffit donc pas qu'un fait puisse être considéré seulement comme une hypothèse possible. Il n'existe pas, en droit des assurances sociales, un principe selon lequel l'administration ou le juge devrait statuer, dans le doute, en faveur de l'assuré.
4.3 Enfin, il incombe à celui qui réclame des prestations de l'assurance-accidents de rendre plausible que les éléments d'un accident sont réunis. S'il ne satisfait pas à cette exigence, en donnant des indications incomplètes, imprécises ou contradictoires, qui ne rendent pas vraisemblable l'existence d'un accident, l'assurance n'est pas tenue de prendre en charge le cas (<ref-ruling> consid. 4b p. 140 et les références).
5. 5.1 Il est constant que le 2 avril 2010, l'intimé n'était plus assuré contre le risque d'accidents auprès de la CNA. La responsabilité de celle-ci ne saurait donc être engagée pour les suites de la énième luxation à l'épaule gauche qu'il a subie à cette date que s'il est établi au degré de la vraisemblance prépondérante que ces troubles sont en lien de causalité avec un autre accident assuré par la CNA (cf. <ref-ruling> consid. 2c p. 296 et les références; RAMA 1994 n° U 206 p. 327 consid. 2). A cet égard, il n'est plus contesté que lesdits troubles ne sont pas liés à l'accident de la circulation du 16 janvier 1994, qui avait à l'époque causé un autre type de lésion à l'épaule gauche (une fracture de la clavicule).
5.2 En l'occurrence, jusqu'à l'annonce de la rechute du 22 avril 2010 dans le cadre de laquelle B._ a allégué avoir subi par le passé, en 1998 ou 1999, une luxation de l'épaule gauche à la suite d'un choc avec un autre joueur au cours d'un match de football, on ne trouve au dossier aucune déclaration d'accident relative à un événement concernant cette région du corps (excepté l'accident de janvier 1994). Par ailleurs, le seul document médical évoquant un problème à l'épaule gauche est un bref compte-rendu de l'état de santé de B._ établi le 14 mai 2002 par le docteur W._, médecin traitant, à l'intention du médecin-conseil de la Nationale suisse d'assurance. Dans ce compte-rendu, le médecin traitant indique que son patient a été opéré avec succès en 1996 pour une luxation récidivante de l'épaule droite et qu'il a récemment présenté une nouvelle luxation, cette fois de l'épaule gauche, en avril 2002, réduite spontanément. La cause de la luxation n'est pas mentionnée.
5.3 Bien qu'en matière d'accident, les explications d'un assuré sur le déroulement d'un fait allégué soient au bénéfice d'une présomption de vraisemblance, il y a lieu, pour des raisons évidentes de preuve, d'émettre des réserves lorsqu'il existe un intervalle de temps important entre la survenance d'un événement accidentel et sa communication à l'assureur-accidents. En l'espèce, l'écoulement d'au moins huit années depuis les faits rend pratiquement impossible à la CNA de procéder à une instruction sérieuse sur les circonstances du traumatisme initial et, partant, d'effectuer un examen adéquat de sa responsabilité. En outre, il ressort du dossier qu'après son accident de janvier 1994, l'assuré a annoncé à la recourante trois épisodes de luxation à l'épaule droite qui ont finalement donné lieu à une opération en 1996. Il apparaît dès lors surprenant qu'il se soit abstenu d'en faire autant pour son épaule gauche. Quant au compte-rendu du docteur W._, il permet seulement de démontrer que la première luxation de l'épaule gauche a eu lieu en avril 2002. En définitive, la version d'un choc à l'épaule gauche au cours d'un match de football n'est étayé par aucun autre élément de preuve que les seules allégations - très tardives - de l'assuré à un moment où un traitement médical plus important s'imposait à lui. Dans ces conditions, les premiers juges ne pouvaient considérer cette version des faits comme établie au degré de vraisemblance prépondérante. Il incombe donc à l'intimé de supporter l'absence de preuve de l'événement accidentel initial à la base de la déclaration de rechute, si bien que la CNA était fondée à lui refuser des prestations à ce titre.
Le recours se révèle bien fondé.
6. Vu l'issue du litige, les intimés, qui succombent, supporteront les frais judiciaires solidairement entre eux.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis. Le jugement du 19 décembre 2011 de la Cour des assurances sociales du Tribunal cantonal valaisan est annulé et la décision sur opposition du 9 février 2011 de la CNA est confirmée.
2. Les frais de justice, arrêtés à 750 fr., sont mis à la charge des intimés, solidairement entre eux.
3. Le présent arrêt est communiqué aux parties, au Tribunal cantonal valaisan, Cour des assurances sociales, et à l'Office fédéral de la santé publique.
Lucerne, le 14 janvier 2013
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Présidente: Leuzinger
La Greffière: von Zwehl