Faits:
A. A.a Le 1er octobre 2005, X._ (ci-après: l'employée) a été engagée en qualité de chef de clinique FMH par les Hôpitaux Universitaires de Genève (ci-après: les HUG).
Le 28 août 2008, l'employée a mis un terme à son contrat de travail, avec effet au 31 décembre 2008. Elle a alors réclamé le paiement d'heures de travail supplémentaires pour les années 2005 à 2008 et chiffré sa réclamation à 37'332 fr. 55.
Les HUG, par courrier du 14 mai 2009, ont contesté le décompte-horaire fourni par leur ancienne employée.
A.b A la suite de l'extension de la loi sur le travail (LTr) aux médecins assistants (englobant les chefs de clinique avec ou sans titre FMH), les HUG ont précisé dans un "Aide-mémoire" que la LTr était applicable, sauf exceptions qui n'entrent ici pas en ligne de compte, aux collaborateurs des HUG dès le 1er janvier 2005.
Entre 2005 et 2006, l'Association des Médecins d'Institutions de Genève (ci-après: l'AMIG) s'est plainte à deux reprises auprès de l'Office cantonal de l'Inspection et des Relations du Travail (ci-après: l'OCIRT) du non-respect de la LTr dans les services des HUG.
Le 1er novembre 2007, une rencontre a eu lieu entre les représentants de l'OCIRT, du Secrétariat d'Etat à l'Economie (SECO), de l'AMIG et des HUG avec pour objectif de régler les modalités d'application de la LTr pour les médecins internes et chefs de clinique au sein des HUG. Une dérogation à la durée hebdomadaire de 50 heures (cf. art. 9 LTr) a été discutée et différents aménagements ont été proposés par l'OCIRT. L'aménagement principal consistait à permettre aux HUG de calculer la durée maximale de travail de 50 heures sur deux semaines (solution du "lissage sur deux semaines"), et non seulement sur une semaine comme cela est prévu dans la LTr; la limite des 140 heures de travail supplémentaires par année ne devait pas être dépassée. Il résulte toutefois des constatations cantonales que l'AMIG n'a pas donné son accord formel pour que ces aménagements puissent être entérinés par le SECO.
Le 7 novembre 2007, l'OCIRT a néanmoins demandé aux HUG d'organiser le travail des médecins-assistants et chefs de clinique selon les aménagements discutés lors de la séance du 1er novembre 2007. L'OCIRT partait du principe que ces modalités d'application dérogeant à la LTr seraient introduites lors d'une modification de l'ordonnance correspondante envisagée par le SECO et elle fixait aux HUG un délai au 1er octobre 2008 pour s'organiser en conformité avec ces aménagements.
Le 14 décembre 2007, l'AMIG a réagi au courrier de l'OCIRT et sollicité l'intervention du SECO pour ordonner à l'autorité cantonale de prendre des mesures contre les HUG en vue d'assurer le respect de la LTr, en particulier la limite hebdomadaire fixée par l'art. 9 de la loi. Elle précisait que l'aménagement proposé par l'OCIRT constituait une violation de l'art. 9 LTr dès lors qu'aucune autorisation dérogatoire au sens de l'art. 28 LTr n'avait été octroyée (l'AMIG n'ayant pas donné son accord). Elle invitait le SECO à indiquer que la durée maximale de travail était limitée à 50 heures par semaine, sans possibilité de lissage sur une période plus longue.
Le 11 janvier 2008, le SECO a répondu à l'AMIG que l'OCIRT était habilitée à proposer la mesure de lissage sur deux semaines, dès lors que cette autorité avait obtenu l'accord du SECO.
L'Association Suisse des Médecins Assistants et Chefs de Clinique (par courrier du 15 février 2008) et l'AMIG (par courrier du 28 mars 2008) se sont adressés au SECO; ils se sont opposés à l'octroi en faveur des HUG d'une dérogation au titre de l'art. 28 LTr, contestant avoir donné leur accord formel.
Le 8 avril 2008, le SECO a alors constaté que, compte tenu du refus de l'AMIG de consentir au lissage sur deux semaines, aucune dérogation à la LTr ne pouvait être donnée sur la base de l'art. 28 LTr.
Le 15 avril 2008, l'OCIRT a informé les HUG que les propositions discutées lors de la séance du 1er novembre 2007 ne pouvaient être retenues.
Le 19 août 2008, les HUG ont confirmé, à la demande de l'OCIRT, s'être engagés à garantir l'application de la LTr aux médecins internes et chefs de clinique et ils ont informé l'autorité cantonale que leur nouvelle directive entrerait en vigueur le 1er octobre 2008.
B. Devant la juridiction des prud'hommes, l'employée a assigné les HUG en paiement de 35'133 fr. 31, montant finalement réduit à 34'916 fr. 06, intérêts en sus, au titre de paiement de 423 heures de travail supplémentaires entre 2005 et 2008. Elle a expliqué que les HUG, qui n'avaient pas obtenu de dérogation valable, étaient tenus d'appliquer la LTr et que les décomptes d'heures fournis n'avaient jamais été contestés par l'employeur qui les recevaient de façon régulière chaque mois.
Les HUG se sont opposés à la demande considérant que, jusqu'au 1er octobre 2008, ils pouvaient déroger à la LTr conformément aux aménagements proposés par l'OCIRT. Reconventionnellement, ils ont conclu à ce que l'employée soit condamnée à leur verser le montant de 4'884 fr.
Le Tribunal des prud'hommes a procédé à l'audition de plusieurs témoins qui se sont prononcés sur l'application de la LTr au sein des HUG et sur les horaires de travail de l'employée.
Par jugement du 14 octobre 2010, le Tribunal des prud'hommes a condamné les HUG à verser à sa partie adverse la somme brute de 33'922 fr. 90, intérêts en sus; il a débouté les HUG de leur demande reconventionnelle.
Sur appel des HUG, la Chambre des prud'hommes de la Cour de justice du canton de Genève, par arrêt du 12 décembre 2011, a confirmé le jugement entrepris et débouté les parties de toutes autres conclusions. Sur la question du "lissage sur deux semaines", elle a retenu qu'une dérogation à l'art. 9 LTr (maximum de 50 heures de travail par semaine) n'était envisageable qu'aux conditions fixées à l'art. 28 LTr. Selon cette dernière disposition, la dérogation n'est possible que si la majorité des travailleurs ou leur représentation dans l'entreprise a manifesté son consentement. La cour précédente a constaté qu'en l'espèce l'AMIG n'avait pas donné son accord formel, ce qui excluait toute dérogation à la LTr; partant, le SECO ne pouvait ratifier les propositions de l'OCIRT et celles-ci étaient alors caduques. Elle a ajouté que les mesures dictées par cette autorité cantonale n'étaient pas contraignantes pour le juge civil, ces mesures consistant en une simple intervention préalable de l'autorité et le juge civil étant lié exclusivement par des décisions bénéficiant d'une force exécutoire. Elle a en outre relevé que la dérogation proposée, ayant été refusée par l'autorité fédérale, ne pouvait être délivrée par l'autorité cantonale; enfin, elle a laissé entendre que le juge civil était libre de se prononcer dans un domaine (prétentions invoquées par un particulier en application de la LTr) de sa compétence (la LTr fondant des "compétences parallèles" entre les autorités administratives et les juridictions civiles).
C. Les HUG exercent un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal du 12 décembre 2011. Sous suite de frais et dépens, ils concluent à son annulation et au renvoi de la cause à l'autorité précédente, ou "si mieux n'aime le Tribunal fédéral", à ce qu'il soit dit que l'employée n'a droit au paiement d'aucune heure supplémentaire et d'aucune heure de travail supplémentaire. Les recourants invoquent une transgression de leur droit d'être entendus (art. 29 al. 2 Cst.), l'arbitraire dans l'établissement des faits (art. 9 Cst.), ainsi que la violation du principe de la bonne foi (<ref-law>).
L'intimée conclut, sous suite de frais et dépens, au rejet du recours.

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé dans ses conclusions libératoire et reconventionnelle (<ref-law>) et dirigé contre un arrêt final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire pécuniaire en matière de droit du travail dont la valeur litigieuse atteint le seuil de 15'000 fr. (<ref-law>), le recours est en principe recevable puisqu'il a été déposé dans le délai (art. 48 al. 1 et 100 LTF) et la forme (<ref-law>) prévus par la loi.
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. Il peut donc également être formé pour violation d'un droit constitutionnel (<ref-ruling> consid. 2.1 p. 247; <ref-ruling> consid. 2.4 p. 313).
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, il 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 (ATF <ref-ruling> consid. 2.4 p. 314; <ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401) - ou en violation du droit au sens de l'<ref-law> (<ref-law>). Il incombe à la partie recourante, qui entend s'écarter des constatations de l'autorité précédente, d'expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (<ref-ruling> consid. 1.4 p. 287 s. et consid. 6.2 p. 288). Une rectification de l'état de fait ne peut être demandée que si elle est de nature à influer sur le sort de la cause (<ref-law>).
En l'espèce, les recourants, aux pages 3 à 6 de leur mémoire, présentent un bref rappel des faits, soulignant que l'état de fait établi par la cour cantonale "se révèle sommaire, voire même partisan". Dans cette partie de leur mémoire, ils ne montrent cependant pas de manière précise quels faits pertinents auraient été retenus ou omis en contradiction manifeste avec le résultat univoque de l'administration des preuves (cf. arrêt 4A_132/2011 du 1er juin 2011 consid. 1.3 et la référence). En conséquence, ils ne formulent pas avec la précision requise, dans leur rappel des faits, un grief à l'encontre des constatations cantonales (art. 97 al. 1 et 105 al. 2 LTF) et le Tribunal fédéral ne voit aucune raison de s'écarter de l'état de fait contenu dans la décision attaquée (art. 105 al. 1 et 2 LTF).
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2. Les recourants invoquent une violation du droit d'être entendu (art. 29 al. 2 Cst.) sous l'angle de leur droit à une décision motivée.
2.1 La jurisprudence a déduit du droit d'être entendu garanti par l'art. 29 al. 2 Cst. notamment l'obligation pour l'autorité de motiver sa décision, de telle manière que son destinataire puisse en saisir la portée et l'attaquer s'il y a lieu en connaissance de cause (<ref-ruling> consid. 4.1 p. 88; <ref-ruling> consid. 3.1 p. 377).
Le juge n'a cependant pas l'obligation de s'exprimer, dans sa décision, sur tous les faits et tous les arguments juridiques qui ont été présentés; il peut se limiter à exposer les éléments essentiels qui l'ont guidé dans sa décision (<ref-ruling> consid. 3.3.1 p. 677; <ref-ruling> consid. 4.1 p. 88; <ref-ruling> consid. 3.1 p. 377).
2.2 Les recourants reprochent à la cour cantonale de ne pas avoir expliqué pourquoi elle n'a pas suivi leur argumentaire principal, sans toutefois indiquer quels étaient les propos tenus dans cet argumentaire; à défaut de motivation précise, ce pan du grief est irrecevable (cf. supra consid. 1.2).
De l'avis des recourants, l'autorité précédente aurait également dû indiquer pour quels motifs elle a écarté "les principes évoqués par les HUG, à savoir le principe de la sécurité juridique ainsi que le principe de la bonne foi".
S'agissant de ces principes, les recourants ne fournissent une brève motivation qu'en rapport avec celui de la bonne foi, soutenant que le juge civil doit protéger la confiance qu'ils ont placé dans les assurances reçues des autorités administratives. La cour cantonale a expliqué que l'intervention de l'OCIRT du 7 novembre 2007 ne constitue pas une décision, de sorte qu'elle ne lie pas le juge civil. Ensuite, de façon plus générale (et en dehors de la notion de décision), elle a laissé entendre, dans sa motivation relative aux "compétences parallèles", que le juge civil peut statuer librement sur les prétentions émises par les particuliers en application de la LTr, indépendamment des éventuelles mesures commandées par l'intérêt public qui ont pu être prises par les autorités administratives; la motivation permet ainsi de comprendre qu'à défaut d'une décision véritable prise par l'autorité administrative, aucun acte (intervention préalable, assurances données, ...) pris par celle-ci n'empêche le juge civil de statuer librement sur une question qui, comme en l'espèce, relève de sa compétence. Savoir si la motivation présentée est convaincante est une question distincte de celle du droit à une décision motivée (cf. à ce sujet infra consid. 4). Dès lors que l'on peut discerner les motifs qui ont guidé la décision du juge, le droit à une décision motivée est respecté (arrêt 4A_242/2009 du 10 décembre 2009 consid. 4.1 et la référence).
En conséquence, la motivation présentée est suffisante pour comprendre la décision attaquée et il n'y a pas de violation du droit à une décision motivée.
3. Les recourants considèrent que la cour cantonale a établi arbitrairement les faits (art. 9 Cst.) en retenant que les mesures ordonnées par l'OCIRT avaient exclu la solution du lissage sur deux semaines "faute d'avoir été accepté par l'AMIG" (arrêt entrepris p. 8).
3.1 Selon la jurisprudence, l'arbitraire, prohibé par l'art. 9 Cst., ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral n'annulera la décision attaquée que lorsque celle-ci est manifestement insoutenable, qu'elle se trouve en contradiction claire avec la situation de fait, qu'elle viole gravement une norme ou un principe juridique indiscuté, ou encore lorsqu'elle heurte de manière choquante le sentiment de la justice et de l'équité; pour qu'une décision soit annulée pour cause d'arbitraire, il ne suffit pas que la motivation formulée soit insoutenable, il faut encore que la décision apparaisse arbitraire dans son résultat (<ref-ruling> consid. 2.4 p. 5; <ref-ruling> consid. 2.2.2 p. 318 s.; <ref-ruling> consid. 4.2 p. 560).
S'agissant plus précisément de l'établissement des faits et de l'appréciation des preuves, la décision attaquée n'est arbitraire que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, s'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée ou encore si, sur la base des éléments recueillis, il a fait une déduction insoutenable (ATF <ref-ruling> consid. 4.2 p. 560; <ref-ruling> consid. 2.1 p. 9). La partie recourante qui invoque l'arbitraire dans l'appréciation des preuves et l'établissement des faits doit démontrer par une argumentation précise, en se référant si possible à des pièces indiscutables du dossier, que la cour cantonale a retenu ou omis un fait pertinent d'une manière insoutenable (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 2.2 p. 246).
3.2 En l'occurrence, on ne voit pas, sur la base des explications fournies par les recourants, en quoi l'état de fait aurait été dressé de façon insoutenable par la cour cantonale. La quasi-totalité des participants à la réunion du 1er novembre 2007 ont expressément indiqué qu'aucun accord formel de la représentation des travailleurs (AMIG) n'a été communiqué lors de la séance et l'AMIG a répété son désaccord dans une lettre du 14 décembre 2007 adressé au SECO; les recourants ne contestent pas avoir pris connaissance de ce courrier qui les concernait directement.
Quant aux affirmations de l'OCIRT (courrier du 7 novembre 2007), confirmées par le SECO (lettre du 11 janvier 2008), selon lesquelles les HUG devaient concrétiser au sein de l'établissement hospitalier les aménagements (régime dérogatoire à la LTr) proposés par l'OCIRT (avec délai au 1er octobre 2008), elles n'ont pas été ignorées par l'autorité précédente, mais au contraire exposées clairement dans l'arrêt entrepris. Il semble, en réalité, que les recourants reprochent à la cour cantonale de ne pas avoir donné suffisamment de poids aux affirmations de l'OCIRT et du SECO. Selon eux, les HUG pouvaient de bonne foi se fonder sur les assurances données par ces autorités pour organiser les heures de travail des chefs de clinique. Déterminer l'effet de ces assurances dans les circonstances d'espèce ne relève cependant plus de l'établissement des faits, mais il s'agit d'une question de droit (cf. infra consid. 4).
Le grief d'arbitraire dans l'établissement des faits est infondé.
4. Les recourants soulignent que, dans leurs courriers respectifs, l'OCIRT et le SECO, qui a fait sienne la position de l'OCIRT, ont confirmé aux HUG qu'il leur était donné un délai au 1er octobre 2008 pour la mise en conformité de la durée hebdomadaire de 50 heures, en moyenne sur deux semaines (solution du lissage), et de la limite des 140 heures de travail supplémentaires par année. Ils considèrent qu'ils étaient ainsi légitimés à se fonder sur les assurances reçues de l'OCIRT et du SECO quant aux modalités d'application de la LTr et à se prévaloir "du principe de la bonne foi, applicable aussi bien en droit privé qu'en droit public (<ref-law>)".
4.1 A titre préalable, il faut constater que les recourants ne prétendent pas que l'OCIRT aurait pris une décision bénéficiant d'une force exécutoire, de sorte que le juge civil serait lié par la décision de l'autorité administrative. Sur ce point, ils ne contestent pas l'appréciation des magistrats cantonaux selon laquelle l'invitation de l'OCIRT du 7 novembre 2007, faite en vertu de l'art. 51 al. 1 LTr, constituait une simple intervention préalable de l'autorité. Ils laissent toutefois entendre que l'intervention de l'autorité administrative cantonale, confirmée dans un premier temps par le SECO, doit plutôt être assimilée à une promesse effective qui doit aujourd'hui être honorée par l'Etat et, partant, ne saurait être ignorée par le juge civil.
Il n'est en outre pas contesté que les chefs de clinique (y compris l'intimée) sont engagés par les HUG sur la base d'un contrat de droit privé (auquel les <ref-law> s'appliquent) et que les recourants peuvent invoquer le respect du principe de la bonne foi vis-à-vis des autorités puisqu'ils agissent ici en qualité de simple employeur.
4.2 Le principe de la bonne foi était implicitement garanti par la Constitution fédérale du 29 mai 1974, sous l'angle du principe général de l'égalité de traitement (art. 4 aCst.). Il a été développé à l'origine sur la base des concepts propres au droit civil (cf. <ref-law>), et a été étendu par la jurisprudence à l'ensemble des domaines du droit (<ref-ruling> consid. 2 p. 348 s.; AUER/MALINVERNI/HOTTELIER, Droit constitutionnel suisse, Vol. II, Les droits fondamentaux, 2e éd. 2006, p. 544 n. 1161; HANS MERZ, in Berner Kommentar, 1962, no 63 ss ad <ref-law>; ELISABETH CHIARELLO, Treu und Glauben als Grundrecht nach Art. 9 der schweizerischen Bundesverfassung, thèse Berne 2004, p. 99 ss).
S'agissant de l'activité étatique (relation entre organes de l'Etat et particuliers), le principe de la bonne foi est dorénavant explicitement consacré par deux dispositions de la Constitution fédérale du 18 avril 1999, à savoir l'art. 5 al. 3 Cst. (obligation imposée à l'Etat) et l'art. 9 Cst., cette dernière disposition représentant un droit constitutionnel qui peut être invoqué par le justiciable (cf. <ref-ruling> consid. 5.2 p. 261; <ref-ruling> consid. 3a p. 387; MÜLLER/SCHEFER, Grundrechte in der Schweiz, 4e éd. 2008, p. 25; HÄFELIN/HALLER/KELLER, Schweizerisches Bundesstaatsrecht, 7e éd. 2008, § 25 n. 820; CHIARELLO, op. cit., p. 103 s.).
En ce qui concerne les relations entre organes de l'Etat et particuliers, le principe de la bonne foi doit donc être directement rattaché à ces dispositions de la nouvelle Constitution fédérale, qui prennent le relais de l'<ref-law> (ou des principes supérieurs que l'on déduisait de cette disposition) (PAUL-HENRI Steinauer, Le Titre préliminaire du Code civil, in TDPS II/1 2009, p. 183). Les recourants invoquent le principe de la bonne foi en rapport avec de prétendues assurances données par les autorités, et non dans le contexte d'une relation (de droit privé) entre particuliers. Il est donc douteux que leur moyen, tiré de l'<ref-law> et non de l'art. 9 Cst., soit recevable (cf. <ref-law> et supra consid. 1.2). Vu l'issue du recours, la question peut toutefois rester indécise.
4.3 Le principe de la bonne foi garantit à l'administré le droit d'être protégé dans la confiance que celui-ci place légitimement dans les assurances qu'il reçoit des autorités. L'administré peut, à certaines conditions, exiger de l'autorité qu'elle se conforme aux promesses ou aux assurances qu'elle lui a faites et ne trompe pas la confiance qu'il a légitimement placée dans celles-ci. De jurisprudence constante, ces conditions sont les suivantes. Il faut: a) que l'autorité soit intervenue dans une situation concrète à l'égard de personnes déterminées; b) qu'elle ait agi ou soit censée avoir agi dans les limites de sa compétence; c) que l'administré n'ait pu se rendre compte immédiatement de l'inexactitude de l'acte selon lequel il a réglé sa conduite; d) qu'il se soit fondé sur l'acte en question pour prendre des dispositions qui ne peuvent être modifiées sans préjudice; e) que la loi n'ait pas changé depuis le moment où l'assurance a été donnée (cf. <ref-ruling> consid. 6.1 p. 636 s. et les nombreuses références citées; récemment: arrêt 9C_429/2011 du 15 mars 2012 consid. 5.1).
La protection de la confiance qu'on peut avoir dans les assurances données ne peut produire d'effet direct que dans les rapports entre un particulier et les autorités, c'est-à-dire l'Etat (<ref-ruling> consid. 4b p. 169). Il en est ainsi, par exemple, lorsqu'une autorité à laquelle on a recouru admet un recours tardif pour la raison que la juridiction précédente avait indiqué par erreur à la partie intéressée que le délai de recours s'élevait à trente jours, alors qu'il n'était que de vingt jours. Certes, dans cet exemple, la protection de la confiance produit un effet sur la partie adverse puisque cette partie doit procéder sur un moyen qui a été présenté tardivement; il ne s'agit toutefois que d'une simple conséquence de la protection (blosse Reflexwirkung des Schutzes) que l'autorité doit assurer à celui qui a demandé des instructions sur les voies de recours, cela en vertu du principe de la bonne foi qui régit les rapports existant entre elle et lui (cf. <ref-ruling> consid. 4b p. 169; BEATRICE WEBER-DÜRLER, Vertrauensschutz im öffentlichen Recht, thèse d'habilitation Bâle 1983, p. 148 et les références).
En l'occurrence, dans l'hypothèse où les conditions d'application du droit à la protection de la bonne foi seraient réalisées (cf. toutefois infra consid. 4.4), les recourants pourraient, dans leur rapport (direct) avec l'autorité administrative, se prévaloir des assurances que celle-ci leur a fournies. Ce n'est toutefois pas ce que veulent les recourants en l'espèce; ils tentent de donner un effet "transversal" à la protection de la confiance, se prévalant des assurances reçues pour écarter la prétention émise par l'employée (intimée) sur la base de son contrat de travail.
Il faut d'emblée rappeler que l'employée n'a pas participé à la "procédure" administrative durant laquelle des assurances (aménagements proposés par l'OCIRT) ont été données à son employeur. Elle fait valoir ses prétentions sur la base d'un contrat de travail conclu avec les HUG; le régime dérogatoire proposé par l'OCIRT aux HUG est totalement étranger à cette relation contractuelle qui est soumise aux dispositions impératives de la LTr (notamment l'art. 9 LTr).
Cela étant, la situation d'espèce est totalement différente du cas de figure traitant du renseignement erroné donné par l'autorité; le fait que l'employée ne puisse plus faire valoir ses prétentions, selon la thèse défendue par les recourants, n'est pas, comme dans le précédent évoqué, la "simple conséquence", pour l'employée, de la protection que l'autorité doit assurer à l'employeur à qui des promesses ont été faites. Force est ici de constater que les HUG voudraient lier (directement) les tribunaux civils par les assurances qu'elles ont reçues, dans une procédure distincte, de la part des autorités administratives afin de faire obstacle aux prétentions émises par l'employée sur la base de son contrat de travail. Un tel effet juridique sur les prétentions tirées d'une relation contractuelle liant des particuliers ne peut être déduit du principe de la bonne foi (cf. <ref-ruling> consid. 4b p. 169 s.). Admettre un tel effet équivaudrait à accepter que l'employeur puisse faire supporter directement à l'employée le préjudice qu'il a subi du fait des dispositions qu'il a prises lui-même sur la base des assurances (contraire à la loi) qu'il a personnellement reçues de l'autorité administrative. On ne saurait raisonnablement accepter une telle conséquence, ce d'autant plus qu'elle placerait l'employée dans une situation inextricable; en effet, de son côté, celle-ci n'a reçu aucune promesse de l'autorité administrative, et elle ne pourrait invoquer ni la protection de sa bonne foi (cf. arrêt 2C_771/2010 du 22 mars 2011 consid. 5.3) ni aucun autre fondement juridique pour réclamer à l'Etat le préjudice mis à sa charge par l'employeur.
C'est donc à bon droit que la cour cantonale a considéré que le juge civil, qui devait prendre une décision sur les prétentions émises par l'intimée sur la base de son contrat de travail et des règles impératives de la LTr, n'était pas lié par les assurances données par l'autorité administrative.
4.4 Au demeurant, on peut encore rappeler qu'il incombe à l'administré qui entend se plaindre avec succès de la violation d'une promesse d'établir la réalisation de toutes les conditions dont dépend le droit à la protection de la bonne foi (ANDRÉ GRISEL, Traité de droit administratif, Vol. I, 1984, p. 390). Or, il découle des faits établis par la cour cantonale que, même à admettre la compétence de l'OCIRT (qui a reçu dans un premier temps l'appui du SECO) en l'espèce (cf. supra consid. 4.3 condition b), les recourants n'ont pas démontré qu'ils ne pouvaient s'apercevoir du caractère illégal de l'acte selon lequel ils ont réglé leur conduite (cf. supra consid. 4.3 condition c).
Il ressort clairement du texte légal (cf. art. 28 LTr) qu'il ne peut être dérogé aux prescriptions impératives de la LTr qu'avec l'accord des travailleurs (majorité des travailleurs intéressés ou de leurs représentants dans l'entreprise). Or, il résulte des constatations cantonales - qui lient le Tribunal fédéral (<ref-law>) - que, lors de la séance du 1er novembre 2007 durant laquelle l'aménagement des conditions d'application de la LTr a été discuté, les intervenants n'ont pas constaté d'accord de l'AMIG, représentant les travailleurs. Les HUG ne pouvaient ainsi se fier aveuglément aux propositions contenues dans la lettre de l'OCIRT du 7 novembre 2007 et adapter leur organisation selon les modalités d'application de la LTr exposées dans ce courrier, ces aménagements ne respectant manifestement pas les exigences de l'art. 28 LTr. En prêtant l'attention commandée par les circonstances, les HUG, par la simple lecture du texte légal (cf. ATF 5A_704/2011 du 23 février 2012 consid. 8.3.2), auraient dû s'apercevoir de l'erreur commise par l'OCIRT. Dans l'esprit des recourants, il ne pouvait y avoir aucun doute quant au désaccord de l'AMIG, cette association ayant encore expressément contesté, le 14 décembre 2007, la solution du lissage présentée par l'OCIRT (cf. également supra consid. 3.2). Le caractère illégal de l'assurance donnée par l'administration était donc patent et il importe peu à cet égard que la position de l'OCIRT ait été, dans un premier temps, confirmée par le SECO (celui-ci affirmant finalement, le 8 avril 2008, qu'aucune dérogation ne pouvait être octroyée, compte tenu du refus de l'AMIG).
Le moyen, pour autant qu'il soit recevable, doit être déclaré mal fondé.
5. Il résulte des considérations qui précédent que le recours doit être rejeté dans la mesure où il est recevable.
Les frais judiciaires et les dépens sont mis à la charge des recourants, qui succombent (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 à 2'000 fr., sont mis à la charge des recourants.
3. Les recourants verseront à l'intimée une indemnité de 2'500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre civile.
Lausanne, le 21 mai 2012
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Piaget