Faits :
A.
Le 20 juin 2012, le Conseil communal de C._ (ci-après: le Conseil communal) a délivré à A.A._ l'autorisation de construire un chalet sur la parcelle n° xxx de l'ancienne commune de D._ (cette dernière faisant partie, depuis le 1er janvier 2009, de la commune de C._ [ci-après: la Commune]). Cette autorisation indiquait à son chiffre 3.21 que "[l]e présent dossier nécessite la fourniture de 2 places de parc. Celles-ci doivent être accessibles toute l'année. Leur pente n'excédera pas 10%. En cas d'impossibilité de les aménager toutes, une contribution de remplacement de 10'000 fr. par place manquante est exigée dans les 30 jours suivant la délivrance du permis d'habiter. Si la place de parc est située hors de la parcelle de base, il sera exigé une servitude en faveur de l'immeuble construit et de la commune de C._ à inscrire au registre foncier avant l'octroi du permis d'habiter. De manière générale, en cas de non-réalisation des places de parc dues, celles-ci seront facturées".
Le 1er décembre 2016, la police des constructions de la Commune a établi son rapport pour la délivrance du permis d'habiter et d'exploiter relatif au chalet des époux A._. Ce rapport indiquait notamment que les deux places de parc dues par les intéressés ne répondaient pas aux critères de l'autorisation de construire et qu'il fallait que l'emplacement de celles-ci et les servitudes éventuelles soient fournies d'ici la fin juin 2017. La Commune a interpellé les intéressés à deux reprises à ce sujet, la dernière fois en juillet 2017.
Le 18 décembre 2017, après l'évocation par les époux A._ de la possibilité d'aménager une place de parc sur la propriété de la Bourgeoisie de D._, une vision locale a été organisée. A cette occasion, il a été relevé que l'aménagement souhaité n'était pas exclu, pour autant que l'accès au sentier pédestre soit conservé et que le parcage ne cause pas de problème d'accès.
Le 5 février 2018, le responsable du service technique de la Commune a informé les époux qu'une demande d'autorisation de construire une place de parc sur la parcelle visée, qui allait prochainement devenir propriété de la Commune, se heurterait très certainement à un refus, pour des questions de surface de rebroussement et de déblaiement notamment. Il leur était donc proposé de lui soumettre une autre solution quant à l'emplacement des places requises dans les 30 jours.
B.
Par décision du 27 mars 2018, en l'absence de réponse des intéressés, le Conseil communal a octroyé à A.A._ le permis d'habiter et d'exploiter relatif à son chalet, tout en précisant que le rapport pour la délivrance dudit permis du 1er décembre 2016 et les conditions de l'autorisation de construire du 20 juin 2012 faisaient partie intégrante de ladite décision.
Le même jour, la Commune a adressé à A.A._ une facture n° 622.65 portant sur la contribution de remplacement relative à deux places de stationnement, d'un montant total de 20'000 fr., à savoir 10'000 fr. par place manquante.
Le 29 mars 2018, l'épouse de l'intéressé a sollicité de la Commune un délai supplémentaire pour l'obtention des deux places de parc, alléguant que des tractations avec des tiers étaient en cours. Le 11 avril 2018, la Commune a refusé d'accorder la prolongation sollicitée, mais a précisé que, si les places dues étaient fournies dans un délai de 10 ans, la contribution de remplacement serait remboursée.
Par courrier du 19 avril 2018, la Bourgeoisie de D._ a refusé la proposition de création d'une place de parc sur la parcelle visée par les époux A._ (<ref-law>).
Par décision du 31 juillet 2018, le Conseil communal a rejeté la réclamation que les époux avaient formé à l'encontre de la contribution de remplacement litigieuse, mais a remplacé la facture n° 622.65 par une nouvelle facture n° 622.70 au nom des deux époux.
Le 30 octobre 2018, les époux ont entamé des nouvelles tractations avec la Bourgeoisie de D._, afin de réaliser les deux places de parc dues sur le fonds de ladite bourgeoisie (<ref-law>).
Par décision du 25 mars 2020, le Conseil d'Etat du canton du Valais a rejeté le recours que les époux avaient formé contre la décision sur réclamation du 31 juillet 2018. Ceux-ci ont interjeté recours auprès du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal). Par arrêt du 22 février 2021, le Tribunal cantonal a rejeté le recours.
C.
Agissant par la voie du recours en matière de droit public, les époux A._ demandent au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 22 février 2021 du Tribunal cantonal et de renvoyer la cause à l'autorité inférieure pour nouvelle décision dans le sens des considérants; subsidiairement, de réformer l'arrêt attaqué dans le sens où ils ne doivent pas s'acquitter de la contribution de remplacement objet de la taxation n° 622.65 [recte: 622.70].
Le Tribunal cantonal renonce à se déterminer sur le recours. La Commune et le Conseil d'Etat du canton du Valais déposent chacun une réponse et concluent au rejet du recours. Les recourants répliquent.

Considérant en droit :
1.
1.1. Le présent litige concerne la perception d'une taxe compensatoire pour places de stationnement. Elle relève donc du droit public au sens de l'<ref-law> (cf. arrêt 2C_761/2019 du 4 février 2020 consid. 1.1). Aucune des exceptions mentionnées à l'<ref-law> n'est en outre applicable. La voie du recours en matière de droit public est partant ouverte.
1.2. Dirigé contre une décision finale (<ref-law>) rendue par un tribunal supérieur statuant en dernière instance cantonale (art. 86 al. 1 let. d et al. 2 LTF), le recours a été déposé en temps utile compte tenue des féries (art. 46 al. 1 let. a et 100 al. 1 LTF) et dans les formes prescrites (<ref-law>). Les recourants, qui ont participé à la procédure devant l'instance précédente, sont particulièrement atteints par la décision entreprise et ont un intérêt digne de protection à son annulation ou à sa modification. Ils ont ainsi qualité pour recourir (cf. <ref-law>). Il convient par conséquent d'entrer en matière.
2.
2.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral applique le droit d'office (<ref-law>). Sauf dans les cas cités expressément à l'<ref-law>, le recours devant le Tribunal fédéral ne peut pas être formé pour violation du droit cantonal (ou communal) en tant que tel. Il est uniquement possible de faire valoir que la mauvaise application du droit cantonal ou communal constitue une violation du droit fédéral, en particulier qu'elle est arbitraire au sens de l'art. 9 Cst. ou contraire à un autre droit fondamental (<ref-ruling> consid. 4.4.1). Le Tribunal fédéral n'examine le moyen tiré de la violation de droits fondamentaux que si ce grief a été invoqué et motivé de façon précise par le recourant (<ref-law>; <ref-ruling> consid. 2.4).
2.2. Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits constatés par l'autorité précédente (<ref-law>), hormis dans les cas prévus à l'<ref-law>. Selon l'<ref-law>, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (art. 9 Cst.) - ou en violation du droit au sens de l'<ref-law> et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-ruling> consid. 2). Conformément à l'<ref-law>, la partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. A défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué (<ref-ruling> consid. 2).
En l'occurrence, les recourants reprochent au Tribunal cantonal d'avoir procédé à une généralisation insoutenable en retenant que la topographie complète de la Commune présentait une pente de 30°. La critique frise la témérité, dès lors qu'il ressort expressément de l'arrêt entrepris qu'un tel degré de déclivité concernait spécifiquement le terrain où se situe le chalet des recourants, ainsi que l'emplacement dans lequel ceux-ci alléguaient vouloir aménager leurs places de parc. Quant à la région dans laquelle se trouve le village de D._, l'autorité précédente a retenu qu'elle présentait une "déclivité importante", ce que les recourants ne remettent pas en cause sous l'angle de l'arbitraire.
Pour le reste, hormis des griefs en lien avec une prétendue violation du droit d'être entendu, qui seront examinés ci-dessous (consid. 3), les intéressés se limitent, s'agissant des faits, à des critiques appellatoires ne répondant pas aux exigences de motivation accrues de l'<ref-law>. Le Tribunal fédéral ne peut donc pas en tenir compte. Il sera dès lors statué sur la base des faits tels qu'ils ressortent de l'arrêt attaqué.
3.
Dans un grief formel qu'il convient d'examiner en premier lieu (<ref-ruling> consid. 3), les recourants, invoquant l'art. 29 al. 2 Cst., se plaignent d'une violation de leur droit d'être entendus, en ce que le Tribunal cantonal a refusé de procéder à une vision locale des emplacements de places de parc faisant l'objet de tractations avec la Bourgeoisie de D._, en particulier pour déterminer la déclivité de ceux-ci, et d'ordonner les expertises qu'ils avaient requises. Ils y voient aussi un défaut de motivation de l'arrêt attaqué.
3.1. Le droit d'être entendu (art. 29 al. 2 Cst.) garantit notamment le droit pour l'intéressé d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, lorsque cela est de nature à influer sur la décision à rendre. L'autorité peut toutefois renoncer à procéder à des mesures d'instruction lorsque les preuves administrées lui ont permis de forger sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 5.2.2 et les arrêts cités). Le refus d'une mesure probatoire par appréciation anticipée des preuves ne peut être remis en cause devant le Tribunal fédéral qu'en invoquant l'arbitraire (art. 9 Cst.) de manière claire et détaillée (<ref-law>; arrêt 2C_885/2019 du 5 mars 2020 et l'arrêt cité).
Le droit d'être entendu implique également pour l'autorité l'obligation de motiver sa décision. Il suffit que le juge mentionne, même brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause (<ref-ruling> consid. 3.2.1 et les arrêts cités). L'autorité n'a pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais elle peut au contraire se limiter à ceux qui lui paraissent pertinents (cf. <ref-ruling> consid. 4.2).
3.2. En l'occurrence, le Tribunal cantonal a rejeté les moyens de preuve proposés en considérant en substance que ceux-ci n'étaient pas essentiels pour l'issue du litige.
Les recourants ne discutent pas cette appréciation anticipée des preuves sous l'angle de l'arbitraire, ce qui suffit pour écarter le grief tiré d'une violation du droit d'être entendu en lien avec le refus des mesures probatoires sollicitées. Quoi qu'il en soit, dans la mesure où les recourants ne remettent pas en cause l'exactitude des données de l'Office fédéral de la topographie faisant état d'une pente dépassant les 30° à l'emplacement de leur chalet respectivement des places de parc envisagées, on ne voit pas en quoi le Tribunal cantonal aurait fait preuve d'arbitraire en retenant qu'une vision locale n'apparaissait pas essentielle sous cet angle. Il n'en va pas autrement s'agissant de la première expertise sollicitée par les recourants, en ce qu'elle aurait permis "en lieu et place d'une vision locale" d'apprécier la configuration des lieux. Quant à la seconde expertise concernant la situation des places de parc dans la Commune, dans la mesure où les recourants allèguent qu'elle aurait eu pour but de permettre de chiffrer le montant de la taxe litigieuse de manière "raisonnable et respectant les facteurs légaux", ils s'en prennent à la fixation de la contribution en cause, et en particulier au caractère proportionné de son montant. Ce moyen sera dès lors examiné dans ce contexte (cf. infra consid. 6).
On ne décèle enfin pas en quoi l'autorité précédente aurait violé son devoir de motivation, dans la mesure où l'arrêt explique, sur près d'une page, qu'il ressortait du chiffre 3.21 de l'autorisation de construire du 20 juin 2012 que la taxe litigieuse serait perçue de manière générale en cas de non-réalisation des places de parc dues et que, par ailleurs, s'agissant de places sur fonds d'autrui, une servitude au registre foncier devait être inscrite avant la délivrance du permis d'habiter, si bien que le simple fait de se prévaloir de tractations en cours n'était pas suffisant. Les recourants ont au demeurant parfaitement compris le raisonnement du Tribunal cantonal, puisqu'ils ne manquent pas de le contester et de développer leurs griefs sur ce point. Autre est la question de savoir si ce raisonnement viole le droit, ce qui sera discuté ci-dessous (cf. infra consid. 5.4).
3.3. Sur le vu de ce qui précède, le grief de violation du droit d'être entendu des recourants est rejeté.
4.
Les dispositions déterminantes pour la perception de la contribution de remplacement pour places de stationnement se trouvent, d'une part, dans la loi valaisanne sur les routes du 3 septembre 1965 (LR/VS: RS/VS 725.1) et, d'autre part, au niveau communal, dans le Règlement communal relatif aux places de stationnement de l'ancienne commune de D._ (ci-après: le Règlement; approuvé par l'Assemblée primaire de D._ le 30 mai 1997 et homologué par le Conseil d'Etat le 10 juillet 1997), applicable à défaut d'adoption, par la Commune de C._, d'un règlement communal des constructions ou relatif au parcage des véhicules harmonisé sur l'ensemble du territoire de ladite Commune (cf. arrêt 2C_805/2017 du 23 janvier 2018 consid. 5.3).
4.1. Au niveau cantonal, l'art. 215 al. 1 LR/VS prévoit l'obligation primaire pour le maître d'ouvrage, lors de la construction d'un immeuble notamment dont l'utilisation entraînera un trafic important de véhicules à moteur et dans la mesure commandée par les circonstances, d'aménager sur terrain privé, au besoin en dehors de la zone d'interdiction de bâtir, les places de stationnement et les voies de circulation nécessaires aux visiteurs et aux usagers. Selon l'art. 219 LR/VS, le propriétaire peut également satisfaire à son obligation en faisant notamment aménager sur fonds d'autrui de telles places et voies de circulation; il doit alors inscrire au registre foncier une servitude en faveur de la parcelle à bâtir et de la commune de situation, et à charge de la parcelle avoisinante.
Des exceptions à l'obligation de construire des aires de stationnement peuvent être autorisées pour de justes motifs, notamment lorsque la création de places de parc et de voies de circulation répondant aux prescriptions légales est matériellement impossible ou entraînerait des frais excessifs pour le propriétaire, sans que l'on puisse équitablement exiger de celui-ci qu'il utilise son immeuble à d'autres fins nécessitant une aire de stationnement moins importante (cf. art. 217 al. 1 LR/VS). Les articles 220 et 221 LR/VS sont réservés (al. 2).
Selon l'art. 221a LR/VS, les communes peuvent, par voie de règlement, percevoir auprès du maître d'ouvrage n'ayant pas la possibilité d'aménager des places de stationnement en nombre suffisant, une taxe de remplacement appropriée dont le produit est affecté à la création de places de stationnement (al. 1). Pour fixer le montant de la contribution, il faut tenir compte des facteurs suivants: (a) coût moyen des places privées dans la région en question; (b) possibilité ou obligation de créer des places privées ouvertes ou couvertes selon les cas; (c) diminution de valeur de l'immeuble en raison de l'impossibilité de créer des places de parc adéquates; (d) situation de l'immeuble par rapport à une installation publique existante ou projetée; (e) recettes éventuelles de la commune provenant de ce genre d'installations (al. 2).
4.2. Au niveau communal, l'art. 3 du Règlement consacre l'obligation primaire, pour le maître d'oeuvre, d'établir sur terrain privé un nombre de places de parc fixé par le Règlement lors de l'octroi d'un permis de construire. Selon l'art. 10 du Règlement, une telle obligation s'éteint si les circonstances locales rendent impossible l'aménagement des places de parc ou nécessitent des dépenses disproportionnées (let. a), ou si la création de telles places est contraire à des prescriptions de droit public notamment (let. b).
Libellé "Contribution de remplacement", l'art. 11 du Règlement prévoit que le maître d'oeuvre est tenu de payer à la commune une taxe de remplacement s'il est dispensé totalement ou partiellement, selon l'art. 10, de l'obligation d'établir des places de stationnement. Le versement obligatoire d'une telle taxe se substitue à l'obligation d'aménager des places de stationnement. Le montant de ladite taxe est déterminé par: (a) le coût moyen d'aménagement de places de parc; (b) la possibilité ou l'obligation de créer des places de parc ouvertes ou couvertes selon les cas; (c) la diminution de valeur de l'immeuble en raison de l'impossibilité de créer des places de parc adéquates; (d) la situation de l'immeuble par rapport à une installation publique existante ou projetée; (e) les recettes éventuelles de la Commune provenant de ce genre d'installation. Dans son appréciation, la Commune doit tenir compte du minima de 8'000 fr. et du maxima de 10'000 fr. pour le village de D._, ces montants (valeur 1996) devant être indexés au coût de la vie par tranche de 5%.
5.
Au fond, les recourants, citant l'art. 9 Cst., se plaignent d'une "mauvaise application du droit" et, implicitement, d'une violation du principe de la légalité en matière fiscale (art. 5 al. 1 et 127 al. 1 Cst.).
5.1. Une décision est arbitraire (art. 9 Cst.) lorsqu'elle contredit clairement la situation de fait, qu'elle viole gravement une norme ou un principe juridique clair et indiscuté ou qu'elle heurte d'une manière choquante le sentiment de la justice et de l'équité. Il n'y a pas d'arbitraire du seul fait qu'une solution autre que celle de l'autorité cantonale semble concevable, voire préférable. Pour qu'une décision soit annulée pour cause d'arbitraire, il ne suffit pas que sa motivation soit insoutenable; il faut encore que cette décision soit arbitraire dans son résultat (<ref-ruling> consid. 5.4).
5.2. Le principe de la légalité régit l'ensemble de l'activité de l'Etat (cf. art. 5 al. 1 Cst.). Il revêt une importance particulière en droit fiscal où il est érigé en droit constitutionnel indépendant à l'art. 127 al. 1 Cst. Cette disposition - qui s'applique à toutes les contributions publiques, tant fédérales que cantonales ou communales - prévoit que les principes généraux régissant le régime fiscal, notamment la qualité de contribuable, l'objet de l'impôt et son mode de calcul, doivent être définis par la loi (<ref-ruling> consid. 3.4 et les arrêts cités).
5.3. Les recourants sont d'avis que la taxe de remplacement litigieuse ne peut, à teneur du Règlement, être perçue qu'en cas d'impossibilité matérielle - à savoir, selon eux, "définitive et irréductible" - d'établir les places de parc dues. Sous cet angle, ils reprochent au Tribunal cantonal d'avoir versé dans l'arbitraire en s'abstenant d'examiner la faisabilité de la réalisation des places de parc faisant l'objet de tractations avec la Bourgeoisie de D._ depuis le mois d'octobre 2018, faisabilité dont ils affirment qu'elle serait "proche de la vraisemblance".
5.4. Comme on l'a vu (cf. supra consid. 4.2), l'art. 11 en lien avec l'art. 10 du Règlement prévoit que la taxe de remplacement est due lorsque le maître de l'ouvrage est dispensé, totalement ou partiellement, de son obligation d'établir les places de stationnement requises pour des motifs de fait tenant aux circonstances locales, mais aussi lorsque leur réalisation nécessite de dépenses disproportionnées ou lorsque des raisons juridiques s'y opposent.
Le fait que la perception de la taxe litigieuse est notamment prévue lorsque le maître d'ouvrage n'aménage pas, en raison de coûts disproportionnés, tout ou partie des places de parc requises, suffit pour retenir de manière soutenable que le Règlement ne limite pas une telle perception aux seuls cas d'impossibilité matérielle, dans le sens que lui prêtent les recourants, d'établir les places requises.
Pour le reste, il est constant que, en près de dix ans, les recourants n'ont pas réussi à fournir les places de parc dues, que ce soit sur leur propre terrain ou sur fonds d'autrui. S'agissant des emplacements proposés, il ressort des constatations cantonales dénuées d'arbitraire (<ref-law>) que ceux-ci se situaient dans une pente de 30° et que les intéressés entendaient réaliser les places de parc "sans aucun aménagement particulier" (cf. courrier du 30 octobre 2018; <ref-law>). Les tractations engagées en mars 2018 avec la Bourgeoisie de D._ ont échoué le 19 avril 2018. Quant aux nouvelles tractations débutées en octobre 2018, force est de constater que l'on ne sait pas, trois ans après le début de celles-ci, si elles sont encore en cours ou ont abouti. C'est au demeurant de manière purement appellatoire, et donc irrecevable, que les intéressés affirment que la faisabilité de leur projet serait proche de la vraisemblance. Dans ces conditions, les recourants ne sauraient se prévaloir indéfiniment, sauf à commettre un abus de droit, de négociations prétendument en cours pour se soustraire au paiement d'une contribution due en remplacement de leur obligation primaire d'aménager des places de stationnement, un tel paiement devant par ailleurs s'effectuer, selon l'art. 14 du Règlement, avant la délivrance du permis d'habiter, intervenue en l'espèce en mars 2018. L'absence de prise en compte, par l'autorité cantonale, des tractations débutées en octobre 2018 pour évaluer la faisabilité de l'implantation de places de parc n'aboutit dès lors pas, dans ces conditions, à un résultat manifestement injuste ou à une iniquité choquante.
5.5. Dans une argumentation quelque peu confuse, les recourants se plaignent ensuite d'un "abus de délégation". Ils soutiennent à cet égard que l'art. 221a LR/VS limiterait expressément la possibilité faite aux communes de percevoir une taxe de remplacement au seul cas où le maître d'oeuvre n'a pas eu la possibilité d'aménager les places dues "en nombre suffisant". Or, selon eux, une telle locution impliquerait que l'aménagement desdites places serait dans l'absolu encore possible, et non pas matériellement impossible. En d'autres termes, le législateur cantonal n'aurait pas prévu la faculté, pour les communes, de percevoir une taxe en cas d'impossibilité matérielle d'aménager les places dues; seul le fait de ne les avoir pas aménagées en nombre suffisant permettrait une telle perception. Les recourants affirment ainsi que, dans la mesure où les autorités précédentes "sembl[ai]ent retenir" que l'aménagement des places de stationnement requises était matériellement impossible sur terrain privé ou sur fonds d'autrui, ils auraient été assujettis au paiement de la taxe litigieuse de manière contraire à la clause de délégation contenue à l'art. 221a LR/VS et, implicitement, au principe de la légalité.
5.6. Il ne ressort pas de l'arrêt attaqué, contrairement à ce que prétendent les recourants, que l'autorité précédente se serait fondée sur une prétendue impossibilité matérielle d'aménager les places de parc requises pour justifier la perception de la taxe litigieuse, mais bien plutôt sur l'absence de réalisation des places dues selon l'autorisation de construire délivrée aux intéressés. Quoi qu'il en soit, la critique des intéressés relative à un "abus de délégation" doit être rejetée, pour les raisons suivantes.
L'art. 221a LR/VS vise à délimiter et attribuer une compétence aux communes, conformément au principe inscrit à l'art. 70 al. 2 de la Constitution du canton du Valais du 8 mars 1907 (RS 131.232), selon lequel les communes accomplissent leurs tâches propres et celles que leur attribue la loi (cf. également art. 106 al. 1 de la loi valaisanne sur les communes du 5 février 2004 [LCo/VS; RS/VS 175.1]). En l'occurrence, il s'agit de celle d'adopter une réglementation communale en matière de contributions de remplacement pour places de stationnement (cf. arrêt 2C_761/2019 du 4 février 2020 consid. 6.4 et 6.6). La perception d'une telle taxe ne peut ainsi pas intervenir directement sur le fondement de l'art. 221a LR/VS, mais doit nécessairement s'effectuer sur la base d'une réglementation communale, adoptée, comme en l'espèce, par l'assemblée primaire (cf. supra consid. 4; cf. aussi art. 17 al. 1 LCo/VS; arrêt 2C_761/2019 précité consid. 6.4). Dans ce contexte, les communes disposent d'une liberté de décision relativement importante et sont, partant, autonomes dans l'adoption de ces dispositions et dans leur application (cf. arrêt 2P.337/2005 du 16 novembre 2006 consid. 4.1; cf. également arrêt 2C_761/2019 précité consid. 6.4).
Il en découle que rien n'empêchait dès lors le législateur communal de prévoir, en vertu de son autonomie, la possibilité de perception d'une taxe de remplacement dans les cas où, pour des motifs de fait ou de droit, l'aménagement de telles places serait impossible pour le maître d'oeuvre. On ne voit pas pas en quoi, dans ces conditions, la taxe litigieuse trouverait sa source dans un abus de délégation contraire à l'art. 221a LR/VS. Il convient au contraire de retenir que celle-ci repose sur une base légale formelle suffisante au sens de l'art. 5 al. 1 et 127 al. 1 Cst. (cf. arrêts 1P.586/2004 du 28 juin 2005 consid. 4.1 et les arrêts cités; arrêt 2C_761/2019 précité consid. 6.6).
5.7. Dans ces conditions, les griefs d'arbitraire dans l'application du droit et de violation du principe de légalité doivent être rejetés.
6.
Les recourants considèrent enfin que le montant de la contribution litigieuse est disproportionné.
6.1. Les contributions de remplacement présupposent l'existence d'une obligation primaire, soit d'une obligation de faire qui, à certaines conditions, peut être remplacée par une prestation pécuniaire. Elles doivent compenser l'avantage que représente pour l'assujetti l'absence de réalisation de l'obligation primaire et appartiennent par conséquent de jurisprudence constante aux contributions causales (cf. <ref-ruling> consid. 2; arrêts 2C_761/2019 du 4 février 2020 consid. 5.2; 2C_44/2016 du 29 août 2016 consid. 2.1; 2C_541/2008 du 13 novembre 2009 consid. 4.3 et l'arrêt cité).
En droit des contributions publiques, la jurisprudence a déduit des principes de la proportionnalité et de l'interdiction de l'arbitraire (art. 5 al. 2 et 9 Cst.) deux sous-principes permettant de contrôler le montant de certaines taxes causales: les principes de la couverture des frais (qui ne s'applique pas en matière de taxes de remplacement; cf. <ref-ruling> consid. 6c) et de l'équivalence. Ce dernier principe veut que le montant de la taxe ne soit pas dans un rapport manifestement disproportionné avec la valeur objective de la prestation fournie et reste dans des limites raisonnables (cf. <ref-ruling> consid. 2.2.1; <ref-ruling> consid. 4.2.2; <ref-ruling> consid. 3.3.2). S'agissant des contributions de remplacement pour places de stationnement manquantes, le montant de la taxe doit en principe être calculé en fonction des coûts de construction économisés, moins la diminution de valeur résultant de la perte de l'avantage de disposer de ses propres places de parc. Des critères schématiques, basés sur la probabilité et l'expérience moyenne, peuvent toutefois être appliqués. Il n'est ainsi pas forcément nécessaire de tenir compte des coûts de construction économisés dans le cas concret, mais il est permis de se baser sur des situations moyennes (arrêt 1P.586/2004 du 28 juin 2005 consid. 4.1 et l'arrêt cité).
6.2. En l'espèce, conformément à l'art. 11 du Règlement, le montant de la taxe litigieuse est déterminé selon plusieurs critères, dont le coût moyen d'aménagement de places de parc notamment. En tout état de cause, le calcul du montant de la taxe doit tenir compte d'un montant minimal et maximal fixé schématiquement selon la région concernée. Pour D._, ces minima et maxima (valeur 1996) correspondaient respectivement à 8'936 fr et 11'760 fr. Sous cet angle, le Tribunal cantonal a retenu que, lors de la facturation de la taxe litigieuse en 2018 et sur le vu de l'indexation au coût de la vie prévu à l'art. 11 du Règlement, lesdits minima et maxima étaient de 8'905 fr. et 11'132 fr.
Les recourants ne remettent pas en cause, sous l'angle de l'arbitraire (cf. supra consid. 2.1), le mode de fixation de la taxe compensatoire qui, comme on l'a déjà vu, repose sur une base légale communale suffisante (cf. supra consid. 5.6 in fine). Ils ne prétendent ni a fortiori ne démontrent pas plus que les valeurs minimales et maximales prévues à l'art. 11 du Règlement seraient manifestement disproportionnées pour le village de D._. Ils ne contestent enfin pas que leur chalet respectivement l'emplacement des places de parc envisagées se situent dans une pente dépassant les 30° et que le village précité se trouve, selon les constatations non arbitraires de l'arrêt attaqué (cf. supra consid. 2.2), dans une région de déclivité importante. Sous cet angle, on ne voit pas en quoi il aurait été arbitraire, pour l'autorité précédente, de retenir que les places de parc devraient vraisemblablement être aménagées dans une pente prononcée, ce qui est notoirement de nature à occasionner des frais importants, si bien que le montant de la taxe, qui se situait au demeurant au milieu de la fourchette réglementaire à D._, apparaissait justifié.
A cela s'ajoute qu'il ressort des faits constatés sans arbitraire par l'autorité précédente (cf. supra consid. 2.2) que le Conseil communal a déterminé le montant de la taxe litigieuse en fonction du coût moyen d'aménagement de places de parc dans le village de D._ (valeur du terrain, terrassement, ouvrage de soutènement, infrastructures et superstructures) notamment. Les recourants ne peuvent dès lors être suivis lorsqu'il affirment que ce facteur n'aurait pas été pris en compte par la Commune, respectivement n'aurait pas été mentionné par l'arrêt attaqué.
On relèvera au surplus que le montant exact de la taxe en cause était connu des recourants depuis le prononcé de la décision d'autorisation de construire du 20 juin 2012, contre laquelle les intéressés n'ont jamais recouru. Sous cet angle, on peut se demander s'il n'aurait pas appartenu aux intéressés de contester directement le montant de la contribution litigieuse en recourant contre la décision d'autorisation de construire déjà (cf. arrêts 2P.337/2005 et 2P.338/2005 du 16 novembre 2006 consid. 4.2), au lieu de s'en plaindre, pour la première fois, dans leur recours du 20 septembre 2018 contre la décision sur réclamation du Conseil communal du 31 juillet 2018. La question peut toutefois demeurer ouverte vu l'issue du recours.
Sur le vu de l'ensemble de ce qui précède, il convient d'admettre que le montant de taxe litigieuse, qui reste dans les limites fixées par le Règlement pour D._, n'apparaît pas choquant dans son résultat compte tenu des circonstances de l'espèce. Mal fondé, le moyen tiré de la violation du principe de la proportionnalité doit partant être rejeté.
7.
Les considérants qui précèdent conduisent au rejet du recours. Succombant, les recourants doivent supporter les frais judiciaires, solidairement entre eux (art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'500 fr., sont mis à la charge des recourants, solidairement entre eux.
3.
Le présent arrêt est communiqué au mandataire des recourants, à la Commune de C._, au Conseil d'Etat du canton du Valais et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 9 février 2022
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
La Présidente : F. Aubry Girardin
Le Greffier : H. Rastorfer