Faits :
A.
Le 12 mars 2012, A._ et B.A._ ont déposé une requête d'autorisation d'utilisation du domaine public cantonal auprès du Département de la mobilité, du territoire et de l'environnement de l'État du Valais (ci-après: le Département). Ils ont demandé à pouvoir disposer d'une surface de 20 m2 environ de la parcelle n° 467, mitoyenne à la parcelle n° 452 dont ils sont copropriétaires, à U._, afin de pouvoir y parquer leur véhicule. Le Service des routes et des cours d'eau a délivré un préavis positif.
Par décision du 10 mai 2012, le Département, par son Chef le Conseiller d'État C._, a octroyé l'autorisation requise aux époux A._. Le point 4 du dispositif de la décision précise que "L'autorisation est accordée à bien plaire; elle peut être révoquée en tout temps sans indemnité".
B.
En 2016, E.D._ a acquis les parcelles n° 453 et 455, auxquelles on accède en empruntant le chemin sur lequel les époux A._ parquent leur véhicule.
En date du 26 mai 2017, D._ et E.D._ ont demandé au Département de révoquer l'autorisation d'utilisation du domaine public accordée par décision du 10 mai 2012, au motif que "les manoeuvres sont rendues peu commodes, voire difficiles lorsqu'il y a de la neige, par la présence du véhicule du couple A._". Par lettre du 13 juin 2017, le Service de la mobilité leur a répondu que leur demande ne pouvait pas être acceptée.
Le 28 juin 2018, D._ et E.D._, nouvellement représentés par Me F._, ont derechef requis la révocation de ladite autorisation: ils ont expliqué que la place de parc concernée empiétait sur la moitié de la largeur du chemin, gênait la circulation et l'accès à leurs parcelles, et gênait en hiver le déblaiement régulier et rapide de la neige; ils ont précisé que les époux A._ disposaient de places de parc en suffisance et d'un garage qu'ils utilisaient toutefois comme rangement; ils ont enfin souligné que les circonstances avaient changé depuis 2012, puisqu'ils avaient alors acquis leur chalet d'anciens propriétaires qui ne disposaient que d'un seul véhicule et que le chemin était depuis lors davantage sollicité du fait que leurs enfants accompagnés de leurs conjoints venaient régulièrement leur rendre visite.
Après avoir diligenté une rencontre sur place le 14 novembre 2018, le Service de la mobilité a proposé une solution à l'amiable aux époux A._ et aux époux D._. Les époux D._ l'ont toutefois refusée.
C.
Par décision du 12 août 2019, le Département, par son Chef C._, a annulé l'autorisation délivrée le 10 mai 2012 pour le 30 novembre 2019, motif pris que "le parcage d'un véhicule sur la surface faisant l'objet de l'autorisation du 10 mai 2012 engendre pour les tiers des difficultés d'accès à d'autres parcelles".
Le 23 septembre 2020, le Conseil d'État du canton du Valais a rejeté le recours interjeté par les époux A._.
Par arrêt du 22 mai 2021, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté dans la mesure de sa recevabilité le recours déposé par les époux A._.
D.
Agissant par la voie du recours en matière de droit public, A._ et B.A._ demandent au Tribunal fédéral d'annuler l'arrêt attaqué et de renvoyer l'affaire au Département.
Le Tribunal cantonal renonce à se déterminer sur le recours. Le Conseil d'État, renvoyant à la prise de position du Département, conclut au rejet du recours dans la mesure de sa recevabilité. Les recourants répliquent.

Considérant en droit :
1.
Le recours est dirigé contre une décision prise en dernière instance cantonale dans une cause de droit public au sens de l'<ref-law>, sans qu'aucune des exceptions prévues à l'<ref-law> ne soit réalisée. Il est dès lors recevable comme recours en matière de droit public selon les <ref-law>. Les recourants ont par ailleurs pris part à la procédure devant le Tribunal cantonal. Ils sont particulièrement touchés par l'arrêt attaqué, qui confirme la révocation d'une autorisation d'utilisation du domaine public dont ils bénéficient, et ont un intérêt digne de protection à sa modification ou à son annulation. Leur qualité pour agir au regard de l'<ref-law> est à l'évidence donnée. Les autres conditions de recevabilité étant par ailleurs remplies, il convient d'entrer en matière sur le recours.
2.
Les recourants font valoir que le Chef du Département C._, qui a pris la décision du 12 août 2019 litigieuse, a manqué d'impartialité.
2.1.
2.1.1. Selon l'art. 10 al. 1 de la loi valaisanne du 6 octobre 1976 sur la procédure et la juridiction administratives (LPJA; RSV 172.6), les personnes appelées à rendre ou à préparer une décision doivent se récuser: [...] lorsqu'un parent ou allié, jusqu'au deuxième degré inclusivement, agit comme avocat, représentant ou mandataire de l'une des parties (let. d); s'il existe des circonstances de nature à faire suspecter leur impartialité (let. e).
2.1.2. Le Tribunal fédéral ne revoit l'interprétation et l'application du droit cantonal que sous l'angle de l'arbitraire. Une décision est arbitraire lorsqu'elle viole gravement une norme ou un principe juridique clair et indiscuté, ou lorsqu'elle contredit d'une manière choquante le sentiment de la justice et de l'équité. Le Tribunal fédéral n'a pas à déterminer quelle est l'interprétation correcte que l'autorité cantonale aurait dû donner des dispositions applicables; il doit uniquement examiner si l'interprétation qui a été faite est défendable. Par conséquent, si celle-ci ne se révèle pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation cantonale en cause, elle sera confirmée, même si une autre solution paraît également concevable, voire préférable. De plus, il ne suffit pas que les motifs de la décision attaquée soient insoutenables, encore faut-il que cette dernière soit arbitraire dans son résultat (<ref-ruling> consid. 7.3; arrêt 1C_228/2018 du 18 juillet 2019 consid. 9.1). Dans ce contexte, les recourants sont soumis aux exigences accrues de motivation de l'<ref-law>.
2.2. Les recourants font valoir que le Chef du Département C._ a fait preuve de partialité, du fait que les époux D._ étaient représentés par sa nièce par alliance Me F._. Ils en veulent pour preuves que le Département a opéré un revirement inexplicable de position depuis l'intervention de l'avocate, que celle-ci a adressé sa requête de révocation non pas au Département mais directement au Conseiller d'État et que ce dernier en aurait pris connaissance avant même sa mise en circulation au sein du Département.
Le Tribunal cantonal a considéré que le reproche d'impartialité a été énoncé en termes généraux et relevait du pur procès d'intention. Il a ajouté que Me F._ n'était que la nièce par alliance du Chef du Département C._, que ce lien de parenté relevait du troisième degré et qu'il n'emportait dès lors pas l'obligation de se récuser en application de l'art. 10 al. 1 let. d LPJA.
2.3. En l'espèce, il n'est pas contesté que Me F._ est la nièce par alliance du Chef du Département C._ et que ce lien d'alliance relève du troisième degré. Le Tribunal cantonal n'a dès lors pas procédé à une application arbitraire du droit cantonal, en considérant que C._ n'avait pas à se récuser en application de l'art. 10 al. 1 let. d LPJA et les recourants en sont restés pour le surplus à des suppositions non établies. Ce grief doit donc être rejeté.
3.
Les recourants se plaignent, en substance, tout d'abord, d'une violation de leur droit d'être entendus, ensuite, d'une constatation manifestement inexacte des faits et, enfin, d'une application arbitraire de l'art. 139 LR.
3.1.
3.1.1. Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, d'avoir accès au dossier, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 7.2.2.1 et les arrêts cités). L'autorité peut cependant 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. 4.1 et les arrêts cités).
3.1.2. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law> (<ref-ruling> consid. 4.4.3). Le recourant ne peut critiquer les constatations de fait ressortant de la décision attaquée que si celles-ci ont été effectuées en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte, c'est-à-dire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>; <ref-ruling> consid. 6). Conformément à l'<ref-law>, le recourant doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Les faits et les critiques invoqués de manière appellatoire sont irrecevables (<ref-ruling> consid. 6.3).
3.1.3. Aux termes de l'art. 139 de la loi valaisanne du 3 septembre 1965 sur les routes (LR; RSV 725.1), une autorisation est nécessaire pour l'utilisation du domaine public excédant l'usage commun, notamment si le domaine public est utilisé à des fins industrielles ou commerciales (al. 1). Des autorisations peuvent être révoquées ou modifiées en tout temps et sans indemnité pour de justes motifs, pour des raisons de police ou pour inobservation des conditions et charges fixées (al. 2).
3.2. Les recourants considèrent que leur droit d'être entendus a été violé: d'une part, ils reprochent aux instances précédentes de ne pas avoir donné suite à leur offre de preuve, à savoir une "démonstration sur place"; d'autre part, ils se plaignent du fait que la requête de révocation déposée par Me F._ ne leur a pas été transmise avant que le Département ne statue, nonobstant de réitérées demandes. Ils estiment par ailleurs que les faits ont été constatés de manière manifestement inexacte par les instances intimées, dans la mesure où la difficulté alléguée des manoeuvres n'aurait pas fait l'objet d'une démonstration sur place. Ils soutiennent finalement qu'il n'existerait aucun juste motif au sens de l'art. 139 al. 2 LR pouvant fonder la révocation de l'autorisation précédemment obtenue.
Le Tribunal cantonal, dans l'arrêt attaqué, a estimé qu'une inspection locale n'était pas nécessaire, au vu de l'extrait du Registre foncier et des nombreuses photographies figurant au dossier. Il a principalement retenu que l'autorisation d'utilisation du domaine public avait été accordée uniquement à bien plaire et que l'État du Valais pouvait ainsi librement - sans devoir justifier un quelconque motif - la révoquer. Il a subsidiairement exposé que, même s'il fallait considérer que seules des raisons pertinentes d'intérêt public pouvaient justifier une révocation, de telles raisons existaient bien en l'espèce, eu égard aux tensions de voisinage relevées et aux constatations qui pouvaient être opérées sur la base de photographies.
3.3.
3.3.1. L'argumentation principale du Tribunal cantonal ne résiste pas à l'examen. L'art. 139 al. 2 LR prévoit en effet expressément qu'une autorisation d'utilisation du domaine public ne peut être révoquée que pour de justes motifs, pour des raisons de police ou pour inobservation des conditions et charges fixées. On ne saurait admettre qu'une autorité puisse, simplement en ajoutant dans ses autorisations qu'elles ont été délivrées "à bien plaire", éluder le système légal univoque de la révocation prévu par la norme précitée. Un tel contenu n'est d'ailleurs aucunement prévu par l'art. 138 al. 3 LR, qui dispose que les autorisations peuvent être rattachées à des conditions, assorties de charges et limitées dans le temps. Force est par conséquent de retenir que l'expression "à plein plaire" utilisée dans la décision d'octroi ne permet pas à l'autorité compétente de révoquer, librement, sans devoir justifier un quelconque motif, une autorisation régulièrement octroyée. L'autorité ne dispose en effet pas d'une entière liberté (cf. arrêts 2P.202/1998 du 30 octobre 1998 consid. 3b; 1P.465/1997 du 15 décembre 1997 consid. 3b; cf. MOOR/POLTIER, Droit administratif, vol. II, 2e éd., Berne 2011, ch. 1.2.4.3 p. 91 et 2.4.3.6 p. 396 et les réf. cit.). Le Conseil d'État ne s'y était d'ailleurs pas trompé dans sa décision du 23 septembre 2020, en affirmant que "la révocation doit être motivée par des considérations pertinentes insufflées d'intérêt public et demeurer dans un rapport cohérent avec l'objet même de la décision et de la législation qui la fonde". La motivation principale du Tribunal cantonal n'est donc pas soutenable au vu du droit cantonal. Partant, la révocation en question doit respecter les conditions posées par l'art. 139 al. 2 LR et être justifiée par des justes motifs, par des raisons de police ou par l'inobservation des conditions et charges fixées.
3.3.2. En l'occurrence, les justes motifs retenus tant par le Conseil d'État que par la cour cantonale consistent principalement dans les tensions engendrées entre les voisins et dans l'entrave à l'accès aux garages des époux D._ générée par le parcage du véhicule des époux A._.
Afin que le principe de l'égalité de traitement puisse être respecté, l'existence de justes motifs doit pouvoir être constatée objectivement. Elle ne saurait dépendre de l'appréciation subjective de tiers. Ainsi, le fait que des tensions existent entre voisins à cause de la place de stationnement litigieuse ne saurait en principe constituer en soi un juste motif de révocation.
Quant à l'entrave à l'accès aux garages des époux D._, il sied de constater ce qui suit: en 2012, le Département a octroyé l'autorisation d'utiliser le domaine public, après avoir, aux dires des recourants, effectué une vision locale; l'organe spécialisé de l'État du Valais, à savoir le Service des routes et des cours d'eau, a délivré un préavis positif. En 2017, les époux D._ ont requis du Département qu'il révoque l'autorisation litigieuse; le Service de la mobilité a toutefois refusé d'accéder à cette demande. Ce n'est qu'en août 2019, après l'intervention de Me F._, que le Chef du Département C._ a révoqué l'autorisation, sans aucune motivation, en se fondant sur le dossier dont il disposait. A sa suite, le Conseil d'État et le Tribunal cantonal ont confirmé ladite révocation, en se basant exclusivement sur les plans de situation et les photographies figurant au dossier et en rejetant la requête d'inspection locale formulée par les recourants. La cour cantonale a alors constaté que "pour sortir [du garage] situé dans l'axe du chemin, les intéressés doivent effectuer une marche arrière plutôt délicate vu la place réduite à cause du positionnement de la voiture des recourants alors qu'ils ne peuvent entrer que difficilement dans celui situé perpendiculairement au chemin en marche avant en raison du faible rayon de braquage dont ils disposent". Si les difficultés de manoeuvrer apparaissent manifestes pour la cour cantonale, il n'en allait pourtant pas de même pour le service spécialisé qui a délivré un préavis positif en 2012. En l'occurrence, il apparaît que la cour cantonale ne pouvait, à l'instar du Conseil d'État, apprécier les difficultés de manoeuvre et de déneigement alléguées par les voisins et susceptibles de constituer des justes motifs au sens de l'art. 139 LR, sur la seule base des photographies et des plans figurant au dossier. Les autorités intimées ne pouvaient, sans se fonder sur les constatations opérées lors d'une inspection locale, valablement conclure à l'existence de ces difficultés de manoeuvre et de déneigement. Ainsi, les autorités cantonales ont violé le droit d'être entendus des recourants, en ne procédant pas à une inspection locale. Cette critique doit être admise.
3.3.3. Enfin, les recourants n'ont certes pu prendre connaissance de la requête de révocation déposée le 28 juin 2019 par Me F._ qu'en date du 18 octobre 2019, soit postérieurement à la décision de révocation du 12 août 2019 du Département, lorsque le Conseil d'État leur a donné la possibilité de consulter le dossier. Les recourants ont ainsi pris connaissance de cette requête des voisins et se sont déterminés à ce sujet devant le Conseil d'État, autorité jouissant d'un plein pouvoir d'examen en fait et en droit (cf. art. 47 LPJA). La cour cantonale pouvait ainsi retenir, sans violer le droit fédéral, que s'il y avait eu violation du droit d'être entendu, celle-ci avait été réparée au cours de la procédure cantonale (cf. <ref-ruling> consid. 4.4; arrêt 1C_229/2020 du 27 août 2020 consid. 2.1). Partant, le grief de violation de l'art. 29 al. 2 Cst. doit, dans cette mesure, être écarté.
4.
Il s'ensuit que le recours en matière de droit public doit être admis et l'arrêt cantonal annulé. La cause est renvoyée au Tribunal cantonal à qui il appartiendra de décider s'il entend procéder lui-même à l'inspection locale nécessaire ou s'il désire renvoyer la cause à une instance précédente (Conseil d'État ou Département). Il ne se justifie pas d'allouer aux recourants, qui ne sont pas représentés par un mandataire professionnel, une indemnité à titre de dépens (art. 68 al. 1 et 2 LTF; cf. <ref-ruling> consid. 4; <ref-ruling> consid. 5b).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis; l'arrêt attaqué est annulé et la cause est renvoyée à la Cour de droit public du Tribunal cantonal du canton du Valais, pour nouvelle décision au sens des considérants.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le présent arrêt est communiqué aux recourants, au Conseil d'État du canton du Valais et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 7 février 2022
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Kneubühler
La Greffière : Arn