Faits :
A.
A.a. Les époux G.A._ et B.A._ sont copropriétaires d'une parcelle à xxx sur laquelle ils ont souhaité ériger un chalet. Dans cette perspective, ils ont conclu, le 21 juin 2012, avec C._ Sàrl, dont D._ était l'unique associé gérant, un " contrat relatif aux prestations de l'architecte (s) elon SIA 1002 ". Ce document prévoyait que ladite société était chargée de la réalisation des plans et de la direction des travaux.
A.b. La société F._ SA, dont l'administrateur unique est G._, était en charge des travaux de maçonnerie.
A.c. Dans une lettre du 2 juillet 2013, C._ Sàrl sous la plume de D._ a écrit à F._ SA les lignes suivantes:
" Confirmation transports déblais du chalet A._ à xxx
Comme convenu lors de notre dernier entretien, je te confirme l'acceptation des prix du transport et de la décharge:
- Taxes: CHF 10.- le m3
- Transport: CHF 21.- le m3
Je te rends attentif que les camions ne pourront pas transporter plus que 8 m3 par voyage car il y a le torrent qui passe sous la route et que la commune demande de ne pas charger au-delà de 8 m3 par camion.
Début des transports: Jeudi 4 juillet 2013 à 8h00.
Adresse de facturation: C._ Sàrl....
Libellé de la facture: Transport déblais chalet A._ à xxx.
Le libellé indiqué ci-dessus doit impérativement figurer dans le " concerne " faute de quoi le paiement sera refusé par la banque. "
A.d. C'est cependant une troisième société, à savoir B._ SA, qui a été chargée du transport des déblais du terrassement à la décharge. Savoir qui lui a confié cette tâche n'a pas même été allégué en procédure. Cela étant, l'on sait à tout le moins qu'à une date non précisée, G._ a pris contact avec cette société pour discuter de l'évacuation des déblais du terrassement et du coût y relatif et que C._ Sàrl savait que cette prestation ne serait pas réalisée par F._ SA, mais notamment par B._ SA.
A.e. B._ SA a effectué les transports prévus entre le 4 et le 26 juillet 2013, puis entre le 20 août et le 13 septembre 2013.
A.f. Les bons de livraison de B._ SA ont été signés par E._, fils de D._, qui lui avait demandé de le faire pour C._ Sàrl. L'indication des mètres cubes transportés correspond à ce qui sera facturé par B._ SA et les prix facturés correspondent aux montants indiqués dans la lettre du 2 juillet 2013.
A.g. Le 25 juillet 2013, une entité intitulée H._ pour " yyy ", dont D._ affirmera ultérieurement qu'elle n'était qu'une sous-branche de C._ Sàrl, a adressé à cette dernière une facture d'un montant de 37'044 fr. dont l'objet était " Chalet A._ à xxx 1er acompte sur travaux préparatoires et terrassement ". Au pied de cette facture figurent la mention " vérifié 26 juil. 2013 " et le timbre de C._ Sàrl, avec la signature de D._. Après avoir sollicité de ce dernier des explications sur cette facture, les époux A._ ont fait virer de leur compte bancaire la somme correspondante en faveur de H._, le 7 août 2013.
A.h. Pour ses prestations, B._ SA a adressé à C._ Sàrl deux factures, l'une du 4 octobre 2013 d'un montant de 7'533 fr. et l'autre du 17 octobre 2013 d'un montant de 28'147 fr. 50. Ces factures sont demeurées impayées.
A.i. Le 24 avril 2014, B._ SA a mis en demeure les époux A._ de verser le montant des factures en question, totalisant 35'680 fr. 50. Ces derniers lui ont répondu, le 3 septembre 2014, que " tous les travaux dont il (était) question (avaient) été confiés (...) à l'entreprise H._ qui visiblement les av (ait) sous-traités " à B._ SA, notamment. Celle-ci a fait notifier à chacun des époux un commandement de payer le montant précité avec intérêts, qui a été frappé d'opposition totale.
A.j. La faillite de C._ Sàrl a été prononcée le 22 février 2016.
B.
B.a. Au bénéfice d'une autorisation de procéder, B._ SA a saisi le juge du district de Sierre, le 13 mars 2015, d'une demande tendant à ce que les époux A._ soient condamnés solidairement à lui verser les montants de 7'533 fr. et 28'147 fr. 50 avec intérêts, et à ce que la mainlevée définitive des oppositions formées aux commandements de payer soit prononcée.
Par jugement du 13 mars 2017, le juge du district de Sierre a fait droit à cette demande. Il a estimé que l'historique du chantier permettait de constater que les époux A._ avaient admis que l'architecte puisse négocier et adjuger des travaux pour eux. Dès lors, en donnant son accord pour que B._ SA effectue les travaux d'évacuation des déblais, C._ Sàrl les avait valablement engagés contractuellement. Les défendeurs étaient dès lors redevables des factures de B._ SA correspondant aux prestations qu'elle avait exécutées, soit 7'533 fr. avec intérêts à 5 % l'an dès le 18 novembre 2013 et 28'147 fr. 50 avec intérêts à 5 % l'an dès le 5 novembre 2013 (échéance du délai de paiement de trente jours mentionné dans les factures).
B.b. Saisi d'un appel des défendeurs, le Tribunal cantonal du canton du Valais a, par jugement du 10 juillet 2020, prononcé que la somme dont les époux A._ étaient redevables, soit 35'680 fr. 50 au total, portait intérêts à 5 % l'an dès le 26 avril 2014, date correspondant au lendemain de la réception de l'interpellation de B._ SA au sens de l'art. 102 al. 1 CO. Pour le surplus, il a confirmé le premier jugement sur la base d'un raisonnement distinct.
Les juges cantonaux ont estimé que la demanderesse n'avait introduit dans le procès aucun fait pouvant fonder un rapport de représentation des défendeurs par C._ Sàrl. Il n'avait jamais été allégué que le contrat liant C._ Sàrl et les défendeurs autorisait la première à adjuger, au nom et pour le compte des défendeurs, des travaux aux différents entrepreneurs intervenant sur le chantier. La demanderesse n'avait pas davantage allégué que les défendeurs auraient, d'une quelconque manière, porté à sa connaissance de prétendus pouvoirs de représentation de C._ Sàrl, pas plus qu'elle n'avait évoqué de circonstance dont elle aurait pu, de bonne foi, inférer l'existence de tels pouvoirs. Elle n'avait enfin jamais allégué en procédure que les défendeurs auraient exprimé - ne serait-ce que tacitement - leur volonté d'être liés par l'agissement de leur architecte. Le raisonnement des premiers juges s'avérait dès lors erroné.
En revanche, il pouvait être fait droit à la demande sur la base des règles relatives à l'enrichissement illégitime (art. 62 ss CO). L'action fondée sur l'enrichissement illégitime était réservée par l'art. 39 al. 3 CO en matière de représentation sans pouvoirs; elle pouvait être dirigée aussi bien contre le représentant sans pouvoirs que contre le pseudo-représenté. Il était établi que la demanderesse avait procédé à l'évacuation et au transport des déblais du chantier; les défendeurs avaient dès lors bénéficié de cette prestation, sans bourse délier. Ils s'étaient ainsi enrichis aux dépens de la demanderesse à concurrence du coût des travaux effectués par celle-ci, de sorte qu'ils étaient redevables du montant de ses factures, étant précisé qu'ils ne contestaient ni les quantités de déblais évacués ni les prix unitaires pratiqués.
C.
Les défendeurs recourent en matière civile au Tribunal fédéral. Ils concluent au rejet intégral de la demande, subsidiairement au renvoi du dossier à la cour cantonale pour nouveau jugement.
La cour cantonale a renoncé à se déterminer sur le recours, en se référant aux considérants de son arrêt. L'intimée n'a pas davantage formulé d'observations, se limitant à conclure au rejet du recours.

Considérant en droit :
1.
Les conditions de recevabilité du recours en matière civile sont réalisées sur le principe, notamment celles afférentes à la valeur litigieuse minimale de 30'000 fr. (art. 74 al. 1 let. b LTF) et au délai de recours (art. 46 al. 1 let. b et art. 100 al. 1 LTF).
2.
2.1. Le recours en matière civile peut être exercé pour violation du droit fédéral (art. 95 let. a LTF), y compris le 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 (art. 106 al. 1 LTF). Il n'est donc 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. 318; <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é (art. 108 al. 1 let. b LTF), le Tribunal fédéral n'examine en principe que les griefs invoqués, sauf en cas d'erreurs juridiques manifestes. 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. 2 p. 88; <ref-ruling> consid. 2 p. 116; <ref-ruling> consid. 1.3 p. 584). Par exception à la règle selon laquelle il applique le droit d'office, il n'examine la violation d'un droit constitutionnel que si le grief a été invoqué et motivé de façon détaillée (art. 106 al. 2 LTF; ATF <ref-ruling> consid. 1.4 in fine p. 400 s.).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Il ne peut rectifier ou compléter les constatations de l'autorité précédente que si elles sont manifestement inexactes ou découlent d'une violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF). " Manifestement inexactes " signifie ici " arbitraires " (ATF <ref-ruling> consid. 2 p. 117; <ref-ruling> consid. 1.5 p. 401). Encore faut-il que la correction du vice soit susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF). La critique de l'état de fait retenu est soumise au principe strict de l'allégation énoncé par l'art. 106 al. 2 LTF (<ref-ruling> consid. 2.3 p. 266 et les références).
La partie qui entend attaquer les faits constatés par l'autorité précédente doit expliquer clairement et de manière circonstanciée en quoi ces conditions seraient réalisées (<ref-ruling> consid. 1.3.1 p. 18 et les références). Si elle souhaite obtenir un complètement de l'état de fait, elle doit aussi démontrer, par des renvois précis aux pièces du dossier, qu'elle a présenté aux autorités précédentes en conformité avec les règles de procédure les faits juridiquement pertinents à cet égard et les moyens de preuve adéquats (<ref-ruling> consid. 2 p. 90). Si la critique ne satisfait pas à ces exigences, les allégations relatives à un état de fait qui s'écarterait de celui de la décision attaquée ne pourront pas être prises en considération (<ref-ruling> consid. 1.3.1 p. 18). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF).
Au regard des principes ci-dessus, il ne peut être tenu compte du chapitre " Faits " dans lequel les recourants paraissent vouloir réécrire, pour ainsi dire, les considérants en fait du jugement cantonal, sans se plaindre d'arbitraire.
3.
Le litige porte sur un montant de 35'680 fr. 50 que la demanderesse réclame aux défendeurs au titre du transport des déblais de terrassement qu'elle a effectué depuis leur parcelle jusqu'à la décharge, entre juillet et septembre 2013.
La cour cantonale a exclu que cette obligation puisse reposer sur un contrat liant l'intimée aux recourants. En effet, l'intimée n'avait introduit dans le procès aucun fait pouvant fonder un rapport de représentation des recourants par C._ Sàrl: elle n'avait pas allégué en procédure que le contrat liant C._ Sàrl aux défendeurs autorisait la première à adjuger, au nom et pour le compte des recourants (art. 32 al. 1 CO), des travaux aux différents entrepreneurs, dont elle-même, que les recourants auraient porté à sa connaissance de prétendus pouvoirs de représentation de C._ Sàrl ou qu'elle aurait pu, de bonne foi, inférer de telle ou telle circonstance l'existence de semblables pouvoirs. Ces constatations de fait, que l'intimée ne remet pas en cause, lient le Tribunal fédéral.
Il demeure la question de savoir si cette obligation pourrait se fonder sur les règles relatives à l'enrichissement illégitime (art. 62 ss CO), que l'intimée invoquait à titre subsidiaire. La cour cantonale y a donné une réponse affirmative, au terme d'un raisonnement que les recourants battent en brèche essentiellement pour le motif que leur enrichissement, à supposer qu'il existe, n'est pas dépourvu de cause légitime.
4.
4.1. L'enrichissement illégitime est une source indépendante d'obligation à côté du contrat et de l'acte illicite, dont le but est de corriger les effets du paiement lorsque la situation juridique qui en découle n'est pas conforme à la justice matérielle (ATF 40 II 249 consid. 5 p. 258). Même si les considérations d'équité y jouent un rôle important (<ref-ruling> consid. 9b p. 440 et l'arrêt cité; cf. aussi <ref-ruling> consid. 3c p. 409), les règles sur l'enrichissement illégitime ne sauraient apparaître comme le dernier recours pour remédier à des résultats considérés d'une façon générale comme inéquitables (<ref-ruling> consid. 3d p. 410 et les références citées; BENOÎT CHAPPUIS, in Commentaire romand, Code des obligations I, 2e éd. 2012, n° 13 de l'introduction aux art. 62-67 CO).
4.2. Aux termes de l'art. 62 CO, celui qui, sans cause légitime, s'est enrichi aux dépens d'autrui, est tenu à restitution (al. 1). La restitution est due, en particulier, de ce qui a été reçu sans cause valable, en vertu d'une cause qui ne s'est pas réalisée, ou d'une cause qui a cessé d'exister (al. 2). L'action pour cause d'enrichissement illégitime repose sur quatre conditions, à savoir l'enrichissement d'une personne, l'appauvrissement d'une autre, un rapport de causalité entre ces deux éléments, et l'absence d'une cause légitime ou le paiement d'un indu (arrêts 4A_59/2009 du 7 septembre 2009 consid. 5.3.3.1; 4C.418/2004 du 2 mars 2005 consid. 3.1; 4C.264/1993 du 23 décembre 1993 consid. 4a).
Un enrichissement se fait " aux dépens d'autrui " lorsqu'il entraîne un appauvrissement d'une autre personne. Le champ d'application de l'enrichissement illégitime est limité à des cas nettement déterminés, où l'appauvrissement du créancier résulte directement de l'enrichissement d'une autre personne et où le déplacement de valeur est dénué de cause juridique valable. Il faut que les parties à l'action soient liées par un rapport causal sur lequel l'attribution sans cause valable s'est fondée (<ref-ruling> consid. 3b/aa p. 691 confirmé à l'<ref-ruling> consid. 3a et b p. 407; arrêts 4A_174/2008 du 10 juillet 2008 consid. 5.1; 4C.433/2006 du 5 novembre 2007 consid. 3.1 et les arrêts cités; 4C.31/1998 du 21 décembre 1998 consid. 5b/bb).
4.3. La jurisprudence s'est déjà penchée sur l'application des règles relatives à l'enrichissement illégitime en présence de rapports triangulaires. Leur particularité est de présenter plusieurs relations causales qui peuvent être viciées. Il faut alors déterminer qui peut agir, respectivement être actionné, en enrichissement illégitime.
En matière d'assignation, la possibilité d'une action directe de l'assigné pour cause d'enrichissement illégitime de l'assignataire est exclue en principe, en cas de vices affectant le rapport de couverture, le rapport de valeur ou les deux rapports à la fois (<ref-ruling> consid. 4a p. 113; <ref-ruling> consid. 3a p. 407; <ref-ruling> consid. 3b/aa p. 691). Il faut toutefois réserver le droit de l'assigné de rechercher directement l'assignataire lorsque l'attribution faite par le premier au second est viciée en soi, mais uniquement dans des cas exceptionnels (<ref-ruling> consid. 4a p. 113). Il y a appauvrissement de l'assignant - et non de l'assigné - et enrichissement de l'assignataire, dans les relations triangulaires où le rapport de valeur est vicié.
Le Tribunal fédéral s'est inspiré de ces principes pour résoudre une problématique impliquant un tiers payant à un créancier une dette du débiteur. Le rapport contractuel entre débiteur et créancier ayant été déclaré nul, se posait la question de savoir si le débiteur disposait de la légitimation active pour réclamer au créancier le montant versé par le tiers payant sur la base de l'enrichissement illégitime. Le Tribunal fédéral lui a donné une réponse affirmative, dans la mesure où c'était le rapport liant le débiteur au créancier qui était vicié (arrêt 4C.253/2000 du 30 janvier 2001 consid. 2d), non sans réserver des circonstances exceptionnelles.
Dans des arrêts plus anciens liés au domaine de la construction, le Tribunal fédéral a raisonné en examinant s'il existait une cause valable du point de vue du propriétaire de la parcelle, bénéficiaire de la prestation. Dans une affaire où l'entrepreneur avait agi contre le maître de l'ouvrage (avec lequel il n'était pas lié par contrat) ensuite du non-paiement de ses factures par l'entrepreneur général, il a considéré que les règles sur l'enrichissement illégitime n'étaient pas applicables: les travaux exécutés par l'entrepreneur et qui avaient profité au maître de l'ouvrage étaient compris dans les prestations promises par l'entrepreneur général au maître de l'ouvrage dans un contrat forfaitaire et la validité de ce contrat n'était pas contestée; ainsi l'enrichissement du maître de l'ouvrage résultant des travaux de l'entrepreneur constituait, du point de vue du maître de l'ouvrage, une prestation contractuelle de l'entrepreneur général; il n'était donc pas privé de cause légitime de son point de vue et ne pouvait donner lieu à un enrichissement illégitime de sa part, au sens de l'art. 62 CO (<ref-ruling> consid. 2 p. 134 s.). Le Tribunal fédéral s'était déjà prononcé dans ce sens dans une affaire opposant un entrepreneur à la propriétaire d'une parcelle sur laquelle un troisième s'était engagé envers elle à construire une villa clefs en main pour un prix forfaitaire. Il a observé que, certes, le maître de l'ouvrage se trouvait enrichi à concurrence de la valeur des travaux exécutés par l'entrepreneur en question, mais que cet enrichissement n'était nullement dépourvu de cause légitime puisqu'il trouvait sa contrepartie dans les obligations contractuelles de la propriétaire envers l'entrepreneur général (<ref-ruling> consid. 4b p. 71).
5.
En l'espèce, deux questions se posent avec acuité. La première consiste à déterminer si la prestation que l'intimée a effectuée était ou non dépourvue de cause légitime et la seconde à savoir si les recourants en ont été enrichis.
5.1. La cour cantonale a constaté que C._ Sàrl n'avait pas agi en qualité de représentant direct des recourants (art. 32 ss CO), ce qui implique qu'aucun contrat ne liait les recourants à l'intimée. Il est bien clair que ceci ne scelle pas le raisonnement. Cela étant, l'on peine à suivre celui qui a guidé les juges cantonaux. La citation de l'art. 39 al. 3 CO dans les considérants en droit de l'arrêt attaqué laisse entendre que ceux-ci se sont fondés sur cet article de loi pour procéder à la subsomption. Si tel était le cas, ceci s'avérerait erroné. En effet, cette disposition présuppose que C._ Sàrl a agi vis-à-vis de l'intimée au nom et pour le compte des recourants, sans disposer des pouvoirs nécessaires ( falsus procurator). Or, comme la cour cantonale l'a souverainement constaté dans son arrêt, l'intimée n'a pas allégué régulièrement en procédure que C._ Sàrl aurait déclaré agir au nom et pour le compte de ceux-ci. Ce fait n'est dès lors pas constant et l'art. 39 al. 3 CO inapplicable.
5.2. Que ce soit du point de vue de l'intimée ou des recourants, il n'apparaît pas que la prestation soit dénuée de cause valable. En effet, l'intimée elle-même ne prétend pas avoir effectué cette prestation en vertu d'un accord inexistant ou vicié. Elle a allégué en procédure que: " En cours de chantier (elle) s'est tout de même vu confier les travaux de " transport de déblais " ", en produisant la lettre du 2 juillet 2013 à titre de preuve (let. A.c supra; complément d'office sur la base du dossier). Elle s'est donc prévalue d'un accord, puisque ces travaux lui ont été confiés et qu'elle les a entrepris, mais n'a rien allégué s'agissant de la personne avec laquelle cet accord est intervenu. Il pourrait théoriquement s'agir de C._ Sàrl, dont émane la lettre en question, ou de F._ SA, puisqu'elle fonde ses prétentions contre les recourants sur la base de l'enrichissement illégitime. Ceci n'est pas déterminant dans le cadre de la présente procédure où aucune de ces deux sociétés n'est partie. Toujours est-il que l'on ne cerne guère en quoi cet accord ne serait pas valable et pour quelle raison l'intimée ne pourrait pas diriger ses prétentions contre son cocontractant, quel qu'il soit.
Quant aux recourants, ils ont allégué en procédure que " D._, pour la société C._ Sàrl, (leur) avait toujours affirmé que les travaux de transport de déblais avaient été confiés à la société H._ ", cette dernière n'étant autre que C._ Sàrl elle-même. C'est cette société qu'ils ont rétribuée pour ces mêmes prestations ( supra let. A.g). De leur point de vue, la prestation n'est pas non plus dénuée de cause légitime. Cette cause consiste dans un accord qu'ils avaient avec C._ Sàrl, sur lequel cette dernière s'est fondée pour facturer cette prestation, peu importe si elle s'est servie pour ce faire d'une autre dénomination (" H._ "). L'état de fait n'est donc pas substantiellement différent de celui à la base de l'<ref-ruling> ou de l'<ref-ruling>. La cour cantonale a, certes, estimé qu'un parallèle ne pouvait pas être tiré avec ces deux arrêts. Cela étant, elle a fondé cette conclusion sur le fait que le contrat liant les recourants à C._ Sàrl ne couvrait que la réalisation des plans et la direction des travaux (cf. supra let. A.a). C'est méconnaître que, tant du point de vue de C._ Sàrl que de celui des recourants, la prestation facturée par la première aux seconds repose sur une cause valable, à savoir un accord entre eux deux.
5.3. Un autre élément corrobore le résultat qui se dégage des considérants qui précèdent. Les recourants ne sont pas enrichis par la prestation que l'intimée a effectuée: certes, ils en ont d'une certaine manière bénéficié puisque les déblais de terrassement transportés par l'intimée provenaient de leur parcelle. Cela étant, ils ont payé la facture d'acompte qui y était relative et qui leur a été adressée par C._ Sàrl (" H._ "). C'est dire qu'ils seraient deux fois débiteurs de la même prestation si la demande était admise (dans le même sens, <ref-ruling> consid. 4b p. 71).
5.4. Partant, c'est à tort que la cour cantonale a fait droit à la demande sur la base de l'art. 62 CO, sans qu'il soit nécessaire de discuter les autres griefs des recourants.
6.
Le recours doit être admis, l'arrêt cantonal annulé et la demande de B._ SA intégralement rejetée. L'émolument judiciaire et les dépens de la présente procédure sont mis à la charge de l'intimée qui succombe.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis et l'arrêt cantonal est annulé.
2.
La demande de B._ SA est rejetée.
3.
Les frais de procédure fixés à 2'000 fr. sont mis à la charge de l'intimée.
4.
L'intimée versera aux recourants, créanciers solidaires, une indemnité de 2'500 fr. à titre de dépens.
5.
La cause est renvoyée à la cour cantonale pour nouvelle décision sur les frais et dépens de la procédure cantonale.
6.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Cour civile II.
Lausanne, le 12 janvier 2021
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Juge présidant : Kiss
La Greffière : Raetz