Faits:
A. A._, employée dans le secteur du commerce de détail et membre du syndicat Y._, a été engagée par X._ & Cie (ci-après: X._) tout d'abord en qualité de collaboratrice de vente temporaire du 18 novembre au 24 décembre 2005, puis comme collaboratrice fixe dès le 1er mars 2006.
Par courrier du 18 février 2009, X._ a licencié A._ pour le 30 avril 2009. La lettre de licenciement reproche pour l'essentiel à l'employée une interview qu'elle a donnée à un journal le 24 décembre 2008, dans laquelle elle critique la pratique de l'entreprise (sans la citer) en relation avec l'ouverture nocturne des magasins.
Le syndicat Y._ a contesté ce licenciement, soutenant qu'il intervenait en raison des activités syndicales de A._, qui était représentante des travailleurs au sein de la Commission paritaire professionnelle du commerce de détail. Estimant qu'un tel congé frappe non seulement le travailleur, mais le syndicat lui-même, Y._ a fait valoir qu'un tel licenciement était interdit par l'art. 17 al. 2 de la Convention cadre du commerce de détail, dont Y._ et X._ sont signataires.
La procédure devant la Commission paritaire professionnelle du commerce de détail a été paralysée en raison d'une divergence complète entre les parties.
B. Le 30 avril 2009, le syndicat Y._ a déposé une requête dirigée contre X._ auprès de la Chambre des relations collectives de travail (ci-après: la CRCT), concluant, à titre de mesures provisionnelles, à ce que A._ soit réengagée provisoirement à partir du 1er mai 2009 et, sur le fond, à ce que le licenciement soit annulé et à ce que l'employée réintègre son poste à partir du 1er mai 2009.
X._ a conclu, sur les mesures provisionnelles, à ce que la requête soit déclarée irrecevable, subsidiairement à ce qu'elle soit rejetée; sur le fond, X._ conclut à l'irrecevabilité de la demande, à son rejet, ainsi qu'à la condamnation du syndicat à une amende et à une peine conventionnelle pour avoir violé ses obligations légales et conventionnelles en lien avec l'obligation de maintenir la paix du travail.
Par décision du 26 mai 2009, intitulée "décision sur mesures provisionnelles", la CRCT a déclaré la demande recevable et ordonné la réintégration de A._ jusqu'à droit jugé sur le fond.
C. X._ exerce un recours en matière civile au Tribunal fédéral contre la décision du 26 mai 2009. Elle conclut, sous suite de frais et dépens, à l'annulation de la décision attaquée et à ce que le Tribunal fédéral déclare irrecevable la demande avec requête de mesures provisionnelles; subsidiairement, elle conclut à l'annulation de la décision attaquée et au rejet de la requête sur mesures provisionnelles avec suite de frais et dépens.
Le syndicat Y._ a conclu au rejet du recours dans la mesure où il est recevable avec suite de frais et dépens.
La requête d'effet suspensif présentée par la recourante a été écartée par décision présidentielle du 23 juillet 2009.

Considérant en droit:
1. La décision attaquée, comme le montre son intitulé et son objet, se caractérise comme une décision sur mesures provisionnelles. Rendue par l'autorité saisie d'une demande sur le fond, elle a pour objet de maintenir le statu quo en ce sens que l'employée reste à son poste pour la durée de la procédure, c'est-à-dire jusqu'à droit jugé sur le fond.
Une décision sur mesures provisionnelles ne peut être attaquée devant le Tribunal fédéral qu'en invoquant la violation de droits constitutionnels (<ref-law>). Le Tribunal fédéral ne peut examiner que les griefs d'ordre constitutionnel invoqués et suffisamment motivés par la partie recourante (<ref-law>).
Lorsque des mesures provisionnelles sont prises dans une procédure autonome et indépendante de tout procès sur le fond, elles donnent lieu à une décision finale (<ref-law>); en revanche, si elles sont prises avant ou pendant une procédure principale et ne doivent déployer leurs effets que durant cette procédure (laquelle doit être régulièrement introduite), les mesures provisionnelles ne donnent pas lieu à une décision finale, mais à une décision incidente (<ref-ruling> consid. 3.1 p. 86 s.; cf. également: Message du 28 février 2001 concernant la révision totale de l'organisation judiciaire fédérale, FF 2001 4129 ch. 4.1.4.1). En l'espèce, la décision attaquée se caractérise clairement comme une décision incidente, puisqu'elle a été rendue par une autorité saisie d'une demande sur le fond, qu'elle ne déploie ses effets que durant le procès et qu'elle ne met pas fin à la procédure introduite.
La décision de maintenir l'employée à son poste durant la procédure ne constitue évidemment pas une décision sur la compétence ou sur une demande de récusation (<ref-law>), de sorte qu'elle doit être qualifiée d'autre décision préjudicielle ou incidente au sens de l'<ref-law>.
Le recours au Tribunal fédéral contre une telle décision n'est donc ouvert que si celle-ci peut causer un préjudice irréparable ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (<ref-law>).
Soutenant qu'elle est exposée à un préjudice irréparable, la recourante fait valoir que l'on ne reviendra plus sur les mesures provisionnelles et qu'elle doit payer le salaire de son employée durant la procédure. Elle oublie cependant que l'employée est tenue de fournir son travail en échange du salaire. Dès lors que le montant du salaire a été librement accepté par la recourante, on doit supposer qu'il correspond, à ses yeux, à la valeur du travail fourni. On ne voit donc pas en quoi la continuation du rapport de travail durant la procédure causerait à la recourante un dommage patrimonial. Il incombe à la partie recourante de démontrer que les conditions de recevabilité de son recours sont réunies, notamment qu'elle est exposée à un préjudice irréparable, lorsque cela n'est pas évident (BERNARD CORBOZ, in Commentaire de la LTF, art. 93 n° 18 et les arrêts non publiés cités). En l'occurrence, on ne parvient pas à discerner en quoi consisterait le préjudice irréparable et l'argumentation présentée ne le démontre en rien. Il faut en conclure que le recours n'est pas recevable sur la base de l'<ref-law>.
Il reste à examiner s'il serait recevable en application de l'<ref-law>. Il s'agit de déterminer si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse. Saisie d'une requête de mesures provisionnelles, l'autorité peut soit accorder les mesures sollicitées (totalement ou partiellement), soit les refuser; quelle que soit la décision sur les mesures provisionnelles, la procédure sur le fond ne prend pas fin, mais se poursuit. En conséquence, même s'il statuait différemment sur les mesures provisionnelles, le Tribunal fédéral ne pourrait pas rendre une décision finale, c'est-à-dire une décision qui met fin à la procédure (cf. <ref-law>). En conséquence, la condition alternative de recevabilité prévue par l'<ref-law> n'est pas non plus remplie.
Le recours contre la décision sur mesures provisionnelles est ainsi irrecevable.
2. La décision attaquée contient, dans son dispositif, la formule "déclare la demande recevable". Sachant que la recourante avait également contesté la recevabilité de la requête sur mesures provisionnelles, il faut se référer aux considérants pour essayer de dégager le sens de cette phrase sibylline.
2.1 Au considérant 1, l'autorité cantonale s'est référée à l'art. 9 al. 1 de la loi genevoise concernant la Chambre des relations collectives de travail du 29 avril 1999 (J1 15). Elle a constaté que cette disposition cantonale lui donnait la compétence pour juger tout litige relatif à l'interprétation ou à l'application d'une convention collective de travail à la demande des parties contractantes ou de l'une d'entre elles. Elle a relevé que Y._, la demanderesse, était l'une des parties contractantes. Il apparaît d'autre part (et l'argumentation de la recourante le confirme) qu'il y a entre les parties un litige sur l'interprétation de l'art. 17.2 de la convention collective, plus exactement sur la question de savoir si la violation de l'interdiction figurant dans cette disposition entraîne la nullité du licenciement.
La disposition sur laquelle l'autorité cantonale a appuyé sa compétence (l'art. 9 al. 1) est une norme de droit cantonal. Or, le recours au Tribunal fédéral n'est pas ouvert pour se plaindre d'une violation du droit cantonal, hormis dans le domaine des droits constitutionnels et des droits politiques (<ref-law>). Certes, la recourante pourrait se plaindre d'arbitraire (art. 9 Cst.) dans l'application du droit cantonal (<ref-ruling> consid. 1.2 p. 382 s.; <ref-ruling> consid. 1 p. 203; <ref-ruling> consid. 2.3 p. 466). Elle n'indique cependant pas en quoi l'autorité cantonale aurait statué arbitrairement en constatant que l'intimé était signataire de la convention collective et qu'il y avait un litige portant sur l'interprétation de celle-ci. Il n'y a donc même pas à entrer en matière, faute de motivation suffisante (<ref-law>).
2.2 Au considérant 2, l'autorité cantonale a estimé qu'elle était également compétente sur la base de la convention collective, puisque la procédure devant la commission paritaire n'avait pas abouti. Il s'agit là d'une motivation alternative que la recourante aurait également dû attaquer pour violation des droits constitutionnels (<ref-ruling> consid. 6.3 p. 120 s.). Il n'y a de toute manière pas lieu d'en discuter, puisqu'il ne s'agit que d'une motivation alternative et que la première motivation résiste à l'examen (cf. consid. 2.1).
2.3 Au considérant 3, la cour cantonale a estimé qu'il n'était pas nécessaire "à ce stade" d'examiner si sa compétence pouvait aussi se fonder sur l'art. 9 al. 3 de la loi genevoise. Or, cette question est évidemment d'importance pour statuer sur les conclusions prises au fond par le syndicat, puisque cette disposition lui permet de se prononcer sur un litige concernant les rapports de travail. En disant qu'elle ne tranchait pas la question "à ce stade", l'autorité cantonale a montré qu'elle ne statuait pas définitivement sur sa compétence. Elle s'est bornée à examiner prima facie si sa compétence n'était pas d'emblée exclue, afin de décider si elle pouvait statuer sur la demande de mesures provisionnelles. Cette interprétation est clairement confirmée par le début du considérant 4: "il résulte de ce qui précède qu'il y a lieu d'entrer en matière sur la demande de mesures provisionnelles".
Savoir si l'autorité peut examiner prima facie sa compétence au stade d'une décision sur mesures provisionnelles est une question de procédure. Comme la procédure relève en l'espèce du droit cantonal, il s'agit d'une question que le Tribunal fédéral ne peut pas examiner en l'absence d'un grief formulé de manière précise (<ref-law>).
Dès lors qu'il résulte de l'interprétation de la décision attaquée que l'autorité cantonale ne s'est prononcée que prima facie sur sa compétence pour décider d'entrer en matière sur la requête de mesures provisionnelles, mais qu'elle se réserve, à un stade ultérieur, de réexaminer les fondements de sa compétence et les conclusions qu'elle peut examiner, il faut conclure que la question de la compétence sur le fond n'est pas définitivement tranchée. Dans un tel cas, il ne s'agit pas d'une décision sur la compétence au sens de l'<ref-law> ouvrant la voie d'un recours au Tribunal fédéral (<ref-ruling> consid. 2.2 p. 291).
Savoir si le licenciement d'espèce était motivé par l'activité syndicale de l'employée, si l'interdiction figurant à l'art. 17.2 de la convention collective conduit à la nullité du licenciement et si le syndicat est habilité à conclure en faveur d'un travailleur d'espèce plutôt que de poser un problème théorique d'interprétation sont des questions qui ne sont pas tranchées sur le fond dans la décision attaquée. Il n'appartient pas au Tribunal fédéral de statuer avant l'autorité compétente en première instance.
3. Les frais judiciaires et les dépens sont mis à la charge de la partie qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge de la recourante.
3. La recourante versera à l'intimé une indemnité de 3'500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Chambre des relations collectives de travail du canton de Genève.
Lausanne, le 30 septembre 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le Juge présidant: Le Greffier:
Corboz Piaget