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 (art. 2 CC). L'intimée conclut, sous suite de frais et dépens, au rejet du recours. 