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.

Considérant en droit:
1. 1.1 Interjeté par les recourants qui ont succombé dans leurs conclusions libératoires (<ref-law>) et dirigé contre une décision finale (<ref-law>) rendue en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire dont la valeur litigieuse atteint le seuil de 30'000 fr. (<ref-law>), le recours en matière civile présentement soumis à l'examen du Tribunal fédéral est en principe recevable, puisqu'il a été déposé dans le délai, compte tenu des féries (art. 46 al. 1 let. c et <ref-law>), prévu par la loi.
1.2 Le mémoire de recours doit contenir les conclusions et les motifs à l'appui de celles-ci (<ref-law>). Les motifs doivent exposer succinctement en quoi l'acte attaqué viole le droit (<ref-law>). Pour satisfaire à cette obligation de motiver, le recourant doit discuter les motifs de la décision entreprise et indiquer précisément en quoi il estime que l'autorité précédente a méconnu le droit; il n'est pas absolument indispensable qu'il indique expressément les dispositions légales - le numéro des articles de loi - ou qu'il désigne expressément les principes non écrits de droit qui auraient été violés; il suffit qu'à la lecture de son exposé, on comprenne clairement quelles règles de droit auraient été, selon lui, transgressées par l'autorité cantonale (cf. <ref-ruling> consid. 2.1 p. 245 s.; <ref-ruling> consid. 3.3). En effet, le Tribunal fédéral n'est pas une autorité d'appel qui revoit la situation en opportunité (cf. <ref-ruling> consid. 6.2); il n'est là que pour sanctionner une violation du droit (cf. <ref-law>).
En l'espèce, le mémoire des recourants est très succinctement motivé - et reprend de surcroît quasiment mot à mot les développements présentés dans leur appel cantonal -, à un point tel que sa recevabilité quant à la forme est douteuse. La question peut toutefois demeurer indécise, dès lors que leur recours ne résiste de toute façon pas à l'examen, comme on va le voir ci-après.
1.3 Le recours en matière civile peut être formé pour violation du droit fédéral (<ref-law>), y compris les droits constitutionnels (<ref-ruling> consid. 1.2 p. 382). Saisi d'un tel recours, le Tribunal fédéral applique le droit d'office (<ref-law>) sur la base des faits établis par l'autorité précédente (<ref-law>), sauf s'ils l'ont été de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (ATF <ref-ruling> consid. 4.3) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). Si la partie recourante entend s'écarter des constatations de fait de l'autorité précédente, elle doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> seraient réalisées. A ce défaut, un état de fait divergent de celui de la décision attaquée ne peut être pris en compte (<ref-ruling> consid. 6.2).
2. En résumé, les recourants reprochent à la cour cantonale d'avoir considéré, contrairement au texte du contrat du 25 août 2004 - dont l'art. 6 confirmait selon eux qu'ils n'avaient pas voix au chapitre vis-à-vis des sous-traitants - et à deux arrêts les concernant - dans lesquels la cour cantonale aurait nié qu'ils aient été liés avec des sous-traitants -, que Z._ Sàrl bénéficiait d'un pouvoir de représentation. En d'autres termes, ils font grief aux juges cantonaux d'avoir "accepté arbitrairement" la demande de paiement présentée par l'intimée alors même qu'aucune relation contractuelle, respectivement lien juridique, ne les liaient à cette société, et cela en complète violation des art. 32 à 40 CO et plus spécifiquement de l'<ref-law>. Ils reprochent également à la cour cantonale d'avoir "jugé en une apparence d'équité, alors qu'elle doit juger en droit".
2.1 D'emblée, il y a lieu de relever que les recourants se prévalent en vain de deux arrêts cantonaux. En effet, d'une part, le Tribunal fédéral n'est pas lié par des précédents dont il n'a pas eu à connaître (<ref-ruling> consid. 4.3 p. 34). D'autre part, semblable comparaison n'est pas pertinente, dès lors qu'il s'agit d'examiner chaque cas en fonction des circonstances de l'espèce, de sorte que seule la situation concrète doit être analysée.
2.2 Aux termes de l'<ref-law>, les droits et obligations dérivant d'un contrat fait au nom d'une autre personne par un représentant autorisé passent au représenté. Les effets de la représentation ne naissent que si le représentant dispose du pouvoir de représentation, c'est-à-dire s'il est habilité à faire naître des droits et des obligations directement en faveur et à la charge du représenté, et si le représentant a la volonté d'agir comme tel (<ref-ruling> consid. 1b p. 64).
Dès lors qu'en l'espèce, il résulte de l'état de fait que le contrat conférait un pouvoir de représentation à Z._ Sàrl et que la volonté de celle-ci de représenter les recourants découlait de la lettre du 10 janvier 2005, l'on ne voit pas que la cour cantonale ait violé le droit fédéral en considérant que Z._ Sàrl avait valablement représenté les recourants vis-à-vis de l'intimée et, partant, en reconnaissant que ceux-là étaient les débiteurs de celle-ci.
3. Les considérants qui précèdent commandent le rejet du recours dans la mesure de sa recevabilité, par un arrêt sommairement motivé (art. 109 al. 2 et 3 LTF).
4. Compte tenu de l'issue du litige, les frais judiciaires et dépens sont mis à la charge des recourants - solidairement entre eux -, qui succombent (art. 66 al. 1 et 5 ainsi qu'art. 68 al. 1, 2 et 4 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'500 fr., sont mis à la charge des recourants, solidairement entre eux.
3. Une indemnité de 4'000 fr., à payer à l'intimée à titre de dépens, est mise à la charge des recourants, solidairement entre eux.
4. Le présent arrêt est communiqué aux mandataires des parties et à la Chambre civile de la Cour de justice du canton de Genève.
Lausanne, le 23 mars 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le Président: La Greffière:
Klett Cornaz