Faits: A. Par contrat du 25 août 2004, les époux X._ ont chargé Z._ Sàrl de la construction d'une villa individuelle sur la parcelle dont ils sont copropriétaires au chemin T._, à ...pour un montant forfaitaire de 785'000 francs. Ledit contrat prévoyait que le prix forfaitaire comprenait notamment l'exécution complète de l'ouvrage défini dans le descriptif et les plans annexés, conformément aux éléments du contrat et selon les règles de l'art de la construction (art. 4 let. a). Par ailleurs, les plus ou moins- values résultant d'éventuelles modifications du projet devaient faire l'objet de devis complémentaires et être acceptées par les deux parties avant le début des travaux concernés. Ces devis devaient également comprendre les honoraires liés à ces modifications (art. 8). Z._ Sàrl était libre de choisir les entreprises, artisans et fournisseurs, les contrats, adjudications et commandes étant établis au nom du maître d'ouvrage et exécutés sous le contrôle de Z._ Sàrl. Les instructions ne pouvaient être données que par Z._ Sàrl, le maître d'ouvrage ayant le droit de contrôler l'avancement des travaux et de demander tous les renseignements à Z._ Sàrl mais pas celui de donner des instructions aux entreprises ni de participer aux rendez-vous de chantier hebdomadaires. En revanche, un rendez-vous hebdomadaire devait être organisé par Z._ Sàrl afin que le maître d'ouvrage puisse suivre l'avancement du chantier et se faire expliquer les différentes phases de la construction (art. 6). Les paiements aux entreprises, artisans et fournisseurs devaient être effectués par le compte bancaire du maître d'ouvrage, après signature des bons de paiement établis par la direction des travaux par celle-ci et par le maître d'ouvrage et à condition qu'ils correspondent à l'avancement des travaux (art. 9). Z._ Sàrl s'est enfin engagée à faire payer ponctuellement tous les entrepreneurs, artisans et fournisseurs dans les délais voulus afin d'éviter le dépôt de toute hypothèque légale (art. 10). Pour le surplus, le contrat renvoyait à titre subsidiaire aux normes SIA, notamment la norme 118. Le 26 novembre 2004, Y._ SA a répondu à une soumission de Z._ Sàrl pour des travaux de terrassement, canalisations et introductions. Le nom de la résidence "La T._" apparaissait sous la rubrique "adresse de l'ouvrage", la promotion, la réalisation et la direction des travaux revenant à Z._ Sàrl. Le chantier s'est ouvert à la fin de l'année 2004, mais Z._ Sàrl n'a adjugé les travaux soumissionnés à Y._ SA que par lettre du 10 janvier 2005, dans les termes suivants: "Par la présente, au nom et pour le compte de Monsieur et Madame X._, et représentés par la Société Z._ Sàrl, nous vous conférons l'exécution et la livraison des travaux suivants pour l'objet cité en référence [...]". Le courrier renvoyait pour le surplus aux conditions générales contractuelles et à la norme SIA 118, n'était signé que par Z._ Sàrl et n'a pas été envoyé en copie aux époux X._. Le 28 novembre 2005, Z._ Sàrl a adjugé à Y._ SA un devis complémentaire de 12'912 fr., se référant au "chantier ch. T._ - ...". Y._ SA a terminé les travaux au plus tard le 17 mars 2006, date de l'établissement de sa facture finale, libellée au nom des époux X._, mais envoyée à l'adresse de Z._ Sàrl, à concurrence de 112'549 fr. 60 TTC, dont à déduire deux acomptes déjà réglés, pour le montant total de 38'247 fr. 50, soit un solde final de 74'302 fr. 10. Cette facture a été vérifiée et approuvée par Z._ Sàrl. Le solde de 74'302 fr. 10 est resté impayé. Ni les époux X._, ni Z._ Sàrl n'ont admis être débiteurs de Y._ SA. B. Le 31 août 2007, Y._ SA a requis la condamnation des époux X._ à lui payer 74'302 fr. 10 avec intérêt à 5 % l'an dès le 17 avril 2006, ce à quoi le Tribunal de première instance du canton de Genève a fait droit par jugement du 24 avril 2008. Statuant sur appel des époux X._ par arrêt du 5 décembre 2008, la Chambre civile de la Cour de justice du canton de Genève a confirmé le jugement du 24 avril 2008. Elle a considéré que le contrat conclu entre Z._ Sàrl et les époux X._ prévoyait que les contrats, adjudications et commandes seraient établis au nom des époux X._ (art. 6). Dans la mesure où ceux-ci ne contestaient pas la validité de cet article, la question de la qualification du contrat les liant à Z._ Sàrl pouvait rester indécise. Le fait que les époux X._ n'avaient ni choisi les sous-traitants, ni n'exerçaient d'influence sur le déroulement des travaux ne changeait rien à la question de l'existence d'un pouvoir de représentation donné à Z._ Sàrl, puisqu'ils avaient expressément convenu avec celle-ci que le "maître d'ouvrage" n'était pas autorisé à établir des contacts directs avec les sous-traitants. C'était donc à juste titre que le premier juge avait considéré que Z._ Sàrl était autorisée à conclure des contrats au nom des époux X._ dans le cadre de la construction de leur maison. Il ressortait par ailleurs explicitement de la lettre du 10 janvier 2005 adressée à Y._ SA que Z._ Sàrl agissait au nom et pour le compte des époux X._, si bien qu'elle avait la volonté de les représenter. Pour sa part, Y._ SA avait conscience que Z._ Sàrl agissait au nom et pour le compte d'autrui puisqu'elle avait mentionné, dans son devis complémentaire, le nom de la résidence "La T._" et qu'elle avait libellé sa facture finale au nom des époux X._. C'était à tort que ceux-ci se référaient aux deux arrêts rendus précédemment en leur faveur par la cour cantonale, dès lors que les faits différaient essentiellement de ceux de la présente cause, car Z._ Sàrl n'avait alors pas clairement indiqué aux sous-traitants qu'elle agissait au nom et pour le compte des époux X._. Enfin, ceux-ci ne pouvaient se prévaloir du contrat d'entreprise générale, car il ne concernait que leurs relations avec Z._ Sàrl et constituait une res inter alios acta à l'égard de Y._ SA. Dans la mesure où Z._ Sàrl avait agi dans le cadre du contrat conclu avec les époux X._ le 25 août 2004 et où les conditions de la représentation étaient réunies, c'était avec raison que le premier juge avait retenu que ceux-ci étaient débiteurs du montant que Y._ SA leur réclamait, les époux X._ n'alléguant au demeurant pas que les travaux aient été entachés d'un défaut. C. Les époux X._ (les recourants) interjettent un recours en matière civile au Tribunal fédéral. Ils concluent à l'annulation de l'arrêt du 5 décembre 2008 et au déboutement de leur adverse partie de toutes ses conclusions, avec suite de dépens des instances cantonales et fédérale. Y._ SA (l'intimée) propose le rejet du recours, sous suite de frais et dépens. 