Faits: A. Les époux H.X._ et F.X._ (ci-après: les maîtres) souhaitaient construire une villa dans la commune de ... (VS). Le 23 juillet 2005, iIs ont conclu un contrat d'entreprise générale avec une société qui s'engageait à réaliser l'ouvrage pour le prix forfaitaire de 430'000 fr. Un établissement bancaire leur a accordé un crédit de 342'000 fr. Le contrat d'entreprise a toutefois pris fin le 4 juillet 2006, d'entente entre les parties. L'entreprise générale avait confié l'exécution des travaux de maçonnerie à la société Z._ Sàrl, dont A._ est devenu le gérant en 2008. En juillet 2006, cette société avait déjà achevé le radier de la villa, mais n'avait pas été payée. Le précité a proposé aux maîtres d'assumer la coordination du chantier pour qu'il puisse être mené à son terme et que sa société soit payée. Le 12 juillet 2006, les maîtres, A._ et un architecte se sont réunis pour établir une liste de "prix estimatifs". L'architecte a évalué à 351'125 fr. le montant des travaux restants à réaliser, dont 120'000 fr. pour les travaux de maçonnerie. Au bas de la liste, il était précisé que le "plafond-limite à ne pas dépasser" était de 490'000 fr. Le document a été signé par les maîtres, A._ et un représentant de la banque. Le 30 août 2006, les maîtres, en qualité d'"emprunteurs", et A._, en qualité de "fiduciaire", ont signé avec la banque un "contrat fiduciaire" en vertu duquel celle-ci s'engageait à accorder un crédit de construction de 490'000 fr. Le contrat précisait que la construction était exécutée par Z._ Sàrl (ci-après: l'entreprise). A._ s'engageait notamment à vérifier que les paiements à la charge du compte de crédit servaient exclusivement à la nouvelle construction, à contresigner pour accord chaque disposition des emprunteurs sur le compte de crédit et à informer la banque et les emprunteurs en cas d'indications de dépassements des coûts de la construction. Le 31 août 2006, l'entreprise a adressé aux maîtres une "offre/devis" portant sur un montant total de 130'823 fr. 50 pour des travaux de maçonnerie et de béton. Sur la base de ce document a été élaboré un "contrat d'entreprise", que l'un des maîtres a signé à une date indéterminée, tout comme l'offre/devis du 31 août 2006. Le 15 juin 2007, l'entreprise a adressé aux maîtres une facture pour des travaux de gypserie exécutés dans leur villa. Elle demandait le paiement de 25'290 fr. 75, après déduction de 15'000 fr. d'acomptes versés les 9 octobre 2006 et 30 janvier 2007. Les intéressés ont refusé de payer cette somme. Le total des prélèvements effectués sur le compte de construction a atteint 502'260 fr. 65, intérêts débiteurs et frais bancaires inclus. Le compte a été soldé le 3 mars 2008. Après cette date, les maîtres ont encore versé 8'560 fr. à l'entreprise. Il s'agissait du solde dû pour les travaux fondés sur le contrat d'entreprise précité et l'offre/devis du 31 août 2006. Il n'est pas établi que l'entreprise ait rédigé ou signé des ordres de virement, ni qu'elle ait payé des factures d'entrepreneurs. Les maîtres ont payé directement le coût des travaux effectués, par le débit de leur compte de construction. B. B.a. Le 22 octobre 2010, l'entreprise a actionné les maîtres devant le Juge du district de Sierre. Elle concluait au paiement de 25'290 fr. 75 plus intérêts. Les maîtres ont conclu au rejet et, à titre reconventionnel, au paiement de 22'120 fr. plus intérêts. En cours de procédure, ils ont concédé que le montant réclamé par l'entreprise et la qualité des travaux effectués n'étaient pas en cause; ils estimaient toutefois ne pas en être débiteurs au vu du contrat conclu. Par jugement du 16 avril 2012, le juge de district a rejeté l'action principale et l'action reconventionnelle. Il a considéré que les parties avaient conclu un contrat d'entreprise générale fixant un prix forfaitaire "plafond" de 490'000 fr. Il incombait à l'entreprise de prouver que la facture litigieuse portait sur des frais supplémentaires occasionnés par une modification de commande; or, aucun élément du dossier ne militait en faveur de cette thèse. Quant à la prétention émise à titre reconventionnel, elle n'était pas prouvée. B.b. L'entreprise a déféré cette décision au Tribunal cantonal valaisan. Par jugement du 3 septembre 2013, le Juge de la II e Cour civile a admis l'appel et condamné solidairement les maîtres à verser à l'entreprise 25'290 fr. 75 plus intérêts. En substance, l'autorité précédente a exclu l'existence d'un contrat d'entreprise générale; elle a constaté que les travaux de gypserie ne figuraient pas dans le devis du 12 juillet 2006, qu'il s'agissait de travaux supplémentaires et qu'ils avaient été acceptés par les maîtres, de sorte que l'entreprise avait le droit d'être rémunérée. C. Les maîtres saisissent le Tribunal fédéral d'un recours constitutionnel subsidiaire assorti d'une requête d'effet suspensif. Ils concluent à la réforme du jugement rendu le 3 septembre 2013, en ce sens que l'appel est rejeté. L'entreprise conclut au rejet du recours. L'autorité précédente se réfère à son arrêt. L'effet suspensif a été refusé par ordonnance présidentielle du 20 novembre 2013. 