Faits: A. Les 14 juin 2010 et 14 juin 2011, l'Assemblée primaire de la commune de X._ a approuvé le règlement sur l'utilisation des routes agricoles, forestières et d'alpages (ci-après: le règlement). Celui-ci a été homologué, sous certaines réserves, par le Conseil d'Etat du canton du Valais le 6 juin 2012 (selon publication au Bulletin officiel du canton du Valais du 15 juin 2012). Le règlement a la teneur suivante: "Vu la loi fédérale sur la circulation routière (LCR) déclarant que les cantons sont compétents pour interdire, restreindre ou régler la circulation sur certaines routes. Vu que les cantons peuvent déléguer cette compétence aux communes, sauf à prévoir un recours cantonal (art. 3 al. 2 LCR). Vu l'article 107 de l'ordonnance sur la signalisation routière qui ouvre une voie de recours contre l'adoption de signaux de prescription (2.01 - 2.15 - 2.43). Vu l'article 8 et l'article 9, al. 1 l. a et b de la loi d'application du 30 septembre 1987 de la législation fédérale sur la circulation routière. Vu l'article 15 de la loi fédérale sur les forêts (LFo) et en particulier son alinéa 3 qui dispose que les cantons pourvoient à la signalisation et aux contrôles nécessaires et que là où la signalisation et les contrôles ne suffisent pas, il est possible d'installer des barrières. Vu l'article 13 de l'ordonnance fédérale sur les forêts (OFo). Vu que les cantons jouissent d'une compétence étendue et ne sont liés que par le respect des droits constitutionnels. Vu les articles 25 et 38 de la loi cantonale sur les forêts et les dangers naturels prévoyant notamment que l'entretien des routes forestières utilisées également à d'autres fins incombe aux communes municipales concernées. Vu l'article 21 de la loi cantonale sur la chasse et la protection des mammifères et oiseaux sauvages (LcChP) qui stipule notamment que le canton détermine l'utilisation restrictive des routes par les chasseurs durant la chasse, et entendu que cette utilisation est réglée de manière exhaustive dans le cadre d'un arrêté quinquennal. Vu les articles 15, 23 et 24 de la loi cantonale sur les forêts prévoyant notamment que l'entretien des routes forestières ouvertes au trafic incombe à la commune municipale. Vu l'article 58 du code des obligations instituant une responsabilité particulière pour le propriétaire de routes. Vu l'article 53 al. 3 du règlement de police de la Commune de X._, prévoyant que le conseil municipal est habilité à poser des barrières ou des signaux sur les routes, afin d'interdire l'accès pour des raisons d'environnement ou de dérangement de la faune. Vu le nombre de routes et de kilomètres à entretenir et la nécessité d'encourager le tourisme pédestre, de protéger la faune et la flore et d'endommager le moins possible dites routes. Vu l'article 17, al. 1, de la loi sur les communes, réglant la compétence de l'assemblée primaire. Le Conseil municipal décide d'adopter le présent règlement sur l'utilisation des routes dont l'entretien lui incombe. art. 1 Toutes les routes agricoles, forestières et d'alpages ouvertes à la circulation hors zone à bâtir sur le territoire de la commune de X._, font, en principe, l'objet de mesures de limitation ou d'interdiction de circuler. Une signalisation adéquate «interdiction de circuler sauf autorisation communale» sera posée et homologuée auprès de la CCSR. art. 2 Les routes agricoles, forestières et d'alpages sont classées en deux catégories A routes fermées à la circulation sauf autorisation communale. B routes fermées par une barrière avec une clé ou système équivalent, remis aux ayants droit. Sont notamment considérés comme ayants droit: les propriétaires d'un mayen ou d'une cabane, les exploitants d'un établissement public, les comités et exploitants d'alpages, la police, les gardes-chasse professionnels valaisans, les pompiers, le triage forestier, les Forces motrices de K._, les responsables communaux et bourgeoisiaux, les responsables de remontées mécaniques, les propriétaires de gravière, le personnel de secours en santé humaine et agricole (vétérinaire), ainsi que les exploitants agricoles qui possèdent des parcelles entretenues et qui sont desservies par les routes concernées. art. 3 Les routes sous catégorie A sont toutes les routes agricoles, forestières et d'alpages, hors zone à bâtir, qui ne font pas partie de la catégorie B. Ces routes feront l'objet d'une signalisation adéquate «interdiction de circuler sauf autorisation communale». Les routes sous catégorie B (barrière) sont notamment les suivantes: - L._, M._ [...] art. 4 Sous réserve d'une signalisation contraire et des autorisations exigées par les législations sur les forêts (cf. alinéa 5 ci-dessous) et sur la chasse, les personnes domiciliées à X._ peuvent circuler sur les routes de catégorie A. Le contrôle se fera sur la base des plaques de voiture. Sont, sur demande, mis au bénéfice d'une vignette annuelle gratuite permettant l'utilisation des routes A: - les alpants et les exploitants d'un alpage de X._; - les membres du comité d'alpage et du comité bourgeoisial, non domiciliés; - les responsables cantonaux en charge de l'agriculture, des forêts ou de la chasse; - les exploitants agricoles dont les parcelles sont desservies par les routes concernées; - le personnel de secours, la police, les pompiers, les gardes-chasse, et titulaires de fonctions similaires, ainsi que les personnes en charge d'une fonction publique en lien avec l'endroit. Les autres personnes non domiciliées pourront bénéficier, sur demande, d'une vignette annuelle, à condition de pouvoir justifier d'une raison valable (propriétaires ou ayants droit à l'année d'un mayen, d'une cabane ou d'un établissement public). Elle est remise contre le versement de Fr. 50.00. La vignette comporte l'indication selon laquelle elle n'autorise pas la circulation sur les routes forestières, quand bien même ces dernières sont classées dans la catégorie A. La circulation de véhicules à moteur est autorisée sur les routes forestières uniquement pour accomplir les activités de gestion forestière. Demeurent réservées les autorisations spéciales pouvant être accordées par le service cantonal compétent, ou par le Conseil municipal d'entente avec ce service, conformément à l'article 25, alinéas 2 et 3, de la loi sur les forêts et les dangers naturels du 14 septembre 2011. Les autorisations concernant les routes forestières et celles délivrées aux non domiciliés ne donnent le droit que de circuler sur la route concernée par l'autorisation. art. 5 Pour les routes agricoles, forestières et d'alpages en catégorie B, les bénéficiaires doivent justifier d'une raison valable (propriétaires ou ayants droit à l'année d'un mayen, d'une cabane ou d'un établissement public). Chaque bénéficiaire d'une clé dépose une caution de Fr. 200.- avant la réception de la clé. Le Conseil peut exempter de cette caution certains usagers, notamment les bourgeoisies, le triage forestier et les autorités publiques. S'agissant des routes forestières, les dispositions de l'article 4, alinéa 5, s'appliquent. Les bénéficiaires de clés non domiciliés s'acquitteront chaque année d'une contribution de Fr. 50.- par clé. Les domiciliés sont exemptés de cette contribution. art. 6 Les bénéficiaires (des routes catégorie A ou B, ainsi que des vignettes journalières) s'engagent à respecter également les conditions suivantes: 1. La barrière doit être fermée immédiatement après le passage du véhicule. 2. L'utilisation d'un véhicule lourd (+ 3.5 tonnes) est soumise à autorisation spéciale. 3. La clé ne peut en aucun cas être remise à une personne autre que son conjoint ou son enfant. A défaut, le contrevenant se verra retirer la clé définitivement. 4. L'usager doit circuler à une vitesse adaptée aux circonstances, notamment à la présence de piétons et d'adeptes de VTT. 5. L'usager n'est pas autorisé à emmener des personnes autres que celles séjournant dans le logement desservi. 6. L'usager n'est pas autorisé à emprunter un tracé hors de la route. 7. L'usager s'engage à poser visiblement l'autorisation sur le pare-brise du véhicule. art. 7 L'ouverture des routes d'alpage s'effectue en principe début juin. L'ouverture des routes des mayens exploités par des domiciliés avec des vaches trayantes s'effectue, en principe, à partir de mi-mai. Les routes communales situées en zone avalanche ne sont pas déblayées. art. 8 Les routes forestières sont soumises à la législation forestière et à la signalisation appropriée. art. 9 Le Conseil municipal peut délivrer, aux personnes non domiciliées, une vignette journalière à titre exceptionnel moyennant une contribution de Fr. 15.- par véhicule (personne handicapée, fête de famille, par exemple) sur les routes agricoles ou d'alpages. art. 10 Le Conseil municipal décide souverainement de l'attribution des vignettes et des clés et du classement des routes agricoles et d'alpages après avoir entendu les intéressés ou requis l'autorisation du propriétaire. Il peut autoriser, limiter ou interdire toute circulation pour de justes motifs, durant un temps déterminé, notamment pendant la chasse et lors de manifestations publiques telles qu'inalpes, désalpes, mi-été. Lorsque pour un motif lié à l'exercice de la chasse, le Conseil municipal adopte une disposition particulière limitée dans le temps, celle-ci doit garantir l'égalité de traitement entre tous les chasseurs. Le Conseil municipal règle toutes les autres modalités d'utilisation des routes agricoles et d'alpages. art. 11 Toute infraction au présent règlement qui ne tombe pas sous le coup des législations fédérale ou cantonale, est passible d'une amende de Fr. 300.00 à Fr. 500.00, de la révocation de l'autorisation et de la confiscation de la clé. art. 12 Demeurent réservées les législations spéciales, notamment sur la forêt et la chasse." B. Par acte du 16 août 2012, A._, B._, C._, D._ et E._ ont interjeté un recours en matière de droit public à l'encontre du règlement. Ils concluent, sous suite de frais et dépens, à ce que celui-ci soit intégralement annulé et à ce qu'interdiction soit faite à la Municipalité de X._ de l'appliquer. A titre préalable, ils requièrent que leur recours soit doté de l'effet suspensif. La commune de X._ conclut au rejet du recours dans la mesure où il est recevable. Le Conseil d'Etat propose de le rejeter. Par ordonnance présidentielle du 10 septembre 2012, la requête d'effet suspensif a été rejetée.