Faits:
A. A._, employée dans le secteur du commerce de détail et membre du syndicat X._, a été engagée par Y._ & Cie (ci-après: Y._) 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, Y._ 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 à W._ 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 X._ 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 O._. Estimant qu'un tel congé frappe non seulement le travailleur, mais le syndicat lui-même, X._ a fait valoir qu'un tel licenciement était interdit par l'art. 17 al. 2 de la Convention cadre du commerce de détail (ci-après: CCT), dont X._ et Y._ sont signataires. L'art. 17 al. 2 CCT prévoit qu'il est interdit de discriminer ou de licencier un employé en raison de son activité exercée en qualité de représentant, de délégué syndical ou de membre des commissions du personnel des employés.
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. B.a Le 30 avril 2009, le syndicat X._ a déposé une requête dirigée contre Y._ auprès de la Chambre des relations collectives de travail, 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.
Y._ 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, Y._ 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 Chambre des relations collectives de travail a déclaré la demande recevable et ordonné la réintégration de A._ jusqu'à droit jugé sur le fond.
Le recours en matière civile interjeté au Tribunal fédéral par Y._ contre cette décision a été déclaré irrecevable, par arrêt du 30 septembre 2009.
B.b Par décision du 16 mars 2010, la Chambre des relations collectives de travail a statué sur le fond de la cause. Elle a déclaré la demande déposée le 30 avril 2009 par le syndicat X._ irrecevable; elle a débouté Y._ de ses conclusions reconventionnelles, ainsi que les parties de toute autre conclusion.
C. Le syndicat X._ exerce un recours en matière civile au Tribunal fédéral contre cette dernière décision. Il conclut, sous suite de frais et dépens, à l'annulation de la décision attaquée et à ce qu'il soit ordonné à Y._, sous la menace de la peine d'une amende prévue par l'<ref-law> dirigée contre ses associés, d'annuler le licenciement de A._, de la réintégrer à son poste à partir du 1er mai 2009 et de débouter Y._ de toutes autres ou contraires conclusions. Subsidiairement, il conclut, sous suite de frais et dépens, à l'annulation de la décision attaquée, à ce qu'il soit dit que le syndicat X._ a la qualité pour agir contre Y._ et que les conclusions de sa demande sont recevables, au renvoi de la cause à la Chambre des relations collectives de travail pour nouvelle décision et au déboutement de Y._ de toutes autres ou contraires conclusions.
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 le recourant a été écartée par ordonnance présidentielle du 27 mai 2010.

Considérant en droit:
1.1 1.1.1 Dans les contestations pécuniaires, le recours en matière civile n'est recevable que si la valeur litigieuse s'élève, en règle générale, à 30'000 fr. au moins (<ref-law>).
L'arrêt entrepris, quoique ne contenant aucune indication au sujet de la valeur litigieuse, tranche une contestation civile de nature pécuniaire, puisque la question litigieuse se rapporte à la validité du congé donné à l'employée, au regard de l'art. 17 al. 2 de la CCT - soumis à interprétation.
La valeur litigieuse est déterminée d'après les conclusions restées litigieuses devant l'autorité précédente (<ref-law>); lorsque ces conclusions ne tendaient pas au paiement d'une somme déterminée, le Tribunal fédéral la fixe selon son appréciation (<ref-law>).
En l'espèce, le recourant a requis, devant l'instance cantonale - tout comme d'ailleurs devant le Tribunal fédéral - la réintégration de l'employée à son poste de travail depuis le 1er mai 2009, soit depuis plus d'une année. Au regard des échelles de rémunération annuelle pour le personnel fixe arrêtées dans la CCT (de 43'560 fr. à 46'560 fr.), on obtient une valeur litigieuse supérieure à 30'000 fr., si bien que le recours est recevable au sens de l'<ref-law>.
1.1.2 La décision attaquée a été rendue par la Chambre des relations collectives de travail qui statue en qualité d'instance judiciaire cantonale unique (art. 1 let. d et 9 al. 5 de la loi genevoise du 29 avril 1999 concernant la Chambre des relations collectives de travail [LCRCT; RSG J 1 15]). Si elle s'est prononcée en dernière instance cantonale (<ref-law>), cette autorité n'a pas statué sur recours comme l'<ref-law> l'exige; cette circonstance n'exclut cependant pas le recours au Tribunal fédéral, puisque cette disposition n'est actuellement pas en vigueur, les cantons disposant d'un délai d'adaptation (<ref-law>).
Pour le surplus, le recours, déposé dans le délai (art. 46 al. 1 let. a et art. 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi, a été interjeté par la partie qui a succombé dans ses conclusions (<ref-law>), si bien qu'il est recevable, sous réserve des griefs soumis au Tribunal fédéral.
1.2 Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.4 p. 400). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 1.4 p. 400).
Par exception à la règle selon laquelle il applique le droit d'office, le Tribunal fédéral ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (<ref-law>).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401; <ref-ruling> consid. 8.1. p. 153) - ou en violation du droit au sens de l'<ref-law> (<ref-law>).
Aucun fait nouveau, ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
2. La Chambre des relations collectives de travail s'est déclarée compétente pour connaître du litige qui lui est soumis par le syndicat, en fondant sa compétence sur l'art. 9 al. 1 LCRCT, qui stipule que la chambre est de plein droit compétente 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. A titre de motivation alternative, la Chambre a observé qu'elle était également compétente sur la base de la convention collective. L'autorité cantonale n'a par contre pas examiné sa compétence sous l'angle de l'art. 9 al. 3 LCRCT, qui permet à l'autorité de se prononcer sur un litige concernant les rapports de travail et qui rattache la compétence à la notion de qualité pour agir selon le droit fédéral, estimant qu'un tel examen est inutile pour trancher le litige.
Le recourant ne dénonce aucune violation du droit cantonal, en lien avec l'art. 9 LCRCT, dont l'application ne peut être discutée devant le Tribunal fédéral que sous l'angle de la violation de l'arbitraire (<ref-ruling> consid. 1.2 p. 382 s.; <ref-ruling> consid. 1 p. 203; <ref-ruling> consid. 2.3 p. 466). Il ne prétend en particulier pas que l'autorité cantonale aurait dû fonder sa compétence sur la base de l'art. 9 al. 3 LCRCT.
La Cour de céans n'a donc pas à revenir sur les fondements de la compétence de l'autorité saisie.
3. Le syndicat, qui a saisi l'autorité cantonale, a conclu à l'annulation du licenciement de l'employée et à sa réintégration à son poste au sein de la société intimée. Il a ainsi formulé une conclusion condamnatoire, liée à une question d'interprétation de l'art. 17 al. 2 CCT. L'autorité cantonale l'a bien compris, puisqu'elle a constaté qu'elle était saisie d'un litige "à propos de l'interprétation qu'il y a lieu de donner à l'art. 17.2 de la CCT".
Dans les considérants de l'arrêt entrepris, la cour cantonale a retenu que le syndicat a un intérêt manifeste à faire constater qu'un employeur a violé la convention collective de travail sur un point ou un autre. Elle a toutefois relevé que le même syndicat n'a pas vocation à prendre des conclusions en faveur d'une seule personne et conclut à l'irrecevabilité de la conclusion tendant à la réintégration de l'employée.
En se prononçant sur la conclusion du syndicat en réintégration de l'employée, l'autorité cantonale a pris position sur la qualité pour agir du recourant, qui appartient aux conditions matérielles de la prétention litigieuse. Même si, de manière erronée, l'autorité cantonale a abouti à un prononcé d'irrecevabilité, il convient d'admettre qu'elle a statué sur la qualité pour agir du recourant. La constatation du défaut de cette qualité fait du reste l'objet du présent recours.
4. Le syndicat recourant reproche à l'autorité cantonale, sous l'angle d'une violation du droit fédéral, d'avoir nié sa qualité pour agir à l'encontre de la partie adverse pour exiger la réintégration de sa déléguée syndicale à son poste de travail.
Le syndicat estime avoir la qualité pour agir en justice à l'encontre de l'intimée à plusieurs titres. Il soutient qu'en tant que partie à la convention collective, il est titulaire de droits à l'encontre de l'intimée, également partie contractante, et qu'il peut ainsi agir en justice pour faire respecter les engagements contractuels pris. Il prétend également avoir été atteint, par le licenciement de l'employée, de manière illicite dans ses propres droits de la personnalité au sens de l'<ref-law> et être légitimé à agir en justice sur la base de l'<ref-law> pour faire cesser cette atteinte. Enfin, il fait valoir qu'en tant qu'association professionnelle, il a la légitimation active pour défendre les travailleurs contre les atteintes portées à leurs droits de la personnalité.
4.1 S'agissant de la qualité pour agir des associations professionnelles, la jurisprudence l'a reconnue quand elles entendent défendre un intérêt collectif comprenant non seulement l'intérêt personnel de leurs membres, mais aussi celui des personnes qui, sans compter parmi leurs adhérents, exercent cependant le métier de ces derniers. Toutefois, même dans cette hypothèse, la qualité pour agir des associations est subordonnée à la condition qu'elles soient habilitées par leurs statuts à sauvegarder les intérêts économiques de leurs membres et que ceux-ci aient eux-mêmes qualité pour intenter l'action. Si elles peuvent ester en justice pour défendre les intérêts communs d'une profession, elles ne sauraient en revanche avoir cette qualité pour réclamer la réparation d'un dommage subi par un de leurs membres personnellement (<ref-ruling> consid. 1a p. 83 s.; <ref-ruling> consid. 4b p. 176; <ref-ruling> consid. 3b p. 347 et les références). Ainsi, la jurisprudence soumet la qualité pour agir d'une association professionnelle à la réalisation de trois conditions cumulatives: l'association doit être habilitée par ses statuts à sauvegarder les intérêts économiques de ses membres, ceux-ci doivent eux-mêmes avoir qualité pour intenter action et, enfin, l'association doit défendre un intérêt collectif, lequel concerne la profession en général, ce qui comprend non seulement l'intérêt personnel de ses membres mais aussi celui des personnes qui exercent le même métier, sans toutefois être membres de l'association professionnelle concernée.
La qualité pour agir d'une association professionnelle est également admise lorsque celle-ci dispose d'un droit propre fondé sur l'<ref-law> pour atteinte à ses droits de la personnalité ou que la qualité pour agir lui est reconnue par une disposition de droit fédéral (<ref-ruling> consid. 2 p. 84 s.; <ref-ruling> consid. 3 et 4 p. 171 ss; FABIENNE HOHL, Procédure civile, T. I, Berne 2001, nos 440 et 441, p. 98).
4.2 En l'occurrence, il n'est pas douteux que la conclusion tendant à l'annulation du congé et à la réintégration de l'employée est une conclusion condamnatoire, dont le but n'est pas de servir les intérêts de tous les travailleurs de la profession. On ne voit pas que le licenciement de l'employée serait susceptible de porter atteinte aux droits de la personnalité des travailleurs de la profession concernée. On ne saurait en particulier admettre, dans le cas d'espèce, l'existence d'un intérêt collectif au regard de la liberté syndicale, invoquée par le recourant comme enjeu de la procédure. Il s'ensuit qu'au moins l'une des conditions posées par la jurisprudence pour que le syndicat puisse agir en réintégration de l'employée fait défaut.
Pour le surplus, on ne voit pas que le licenciement de l'employée porte atteinte aux droits de la personnalité du syndicat au sens de l'<ref-law>. Celui-ci ne dispose en effet pas d'un droit propre, fondé sur cette disposition, qui garantirait le maintien de ses membres à leur poste de travail en cas de licenciement intervenant en violation de la convention collective. Il n'apparaît en outre pas que le licenciement de l'employée porte atteinte à la considération sociale du syndicat, en tant que droit reconnu de la personnalité des personnes morales (cf. ATF <ref-ruling> consid. 3a p. 171). On ne discerne du reste pas pourquoi le syndicat aurait conclu en faveur de l'un de ses membres - en demandant la réintégration de celui-ci -, et non pas en constatation de la violation de la convention collective, s'il estimait être atteint dans sa propre personnalité.
Aucune autre disposition de droit fédéral ne trouve par ailleurs application pour fonder la légitimation active du recourant.
C'est donc à bon droit que l'autorité cantonale a nié la qualité pour agir du recourant en ce qui concerne la demande en réintégration.
Le prononcé d'irrecevabilité de la demande, en lieu et place d'un prononcé de rejet, n'est pas en soi contesté. Cela étant, il n'y a pas lieu d'y revenir.
5. Dans la motivation de l'arrêt, les juges cantonaux se sont également prononcés sur la qualité de déléguée syndicale de A._, sur le motif prépondérant de licenciement, sur l'interprétation de l'art. 17 al. 2 CCT et sur la compatibilité de cette disposition conventionnelle avec l'<ref-law>.
Le recourant conteste - pour partie seulement - la position adoptée par la Chambre des relations collectives de travail dans son analyse des arguments au fond. Ainsi, il critique l'incompatibilité de la disposition conventionnelle avec l'<ref-law>. De son point de vue, les art. 336a et 361 CO n'ont pas vocation à s'appliquer dans le présent litige. Il soutient en outre que l'ordre juridictionnel suisse permet l'amélioration par la voie conventionnelle de la protection légale des <ref-law> en matière de licenciement.
Dans la mesure où les juges cantonaux ont nié, à bon droit, la qualité pour agir du recourant, il n'est pas nécessaire d'entrer en matière sur les griefs se rapportant aux arguments de fond du litige.
6. Le recours est rejeté dans la mesure de sa recevabilité.
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 rejeté, dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimée 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 12 juillet 2010
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Klett Crittin