Faits :
A. Le canton du Valais a modifié la Loi d'application de la loi fédérale sur la protection des animaux (ci-après: LcLPA) du 14 novembre 1984, avec effet au 1er janvier 2004. Selon l'art. 24a LcLPA, tout chien âgé de plus de six mois, dont le détenteur est domicilié en Valais, doit être muni d'une puce électronique. L'art. 24b LcLPA dispose ce qui suit au sujet des "chiens dangereux":
"1. Ils sont catalogués en chiens interdits, potentiellement dangereux, jugés dangereux.
2. Le Conseil d'Etat peut édicter une liste de races de chiens et leurs croisements, dont la détention en Valais est interdite.
3. Le Conseil d'Etat édicte une liste de races de chiens potentiellement dangereux et de leurs croisements. Ces chiens doivent toujours être tenus en laisse et munis d'une muselière en dehors de la sphère privée.
4. Tous les chiens signalés par les communes, ceux qui sont désignés par le Service vétérinaire, ainsi que les chiens qui ont fait preuve d'agressivité doivent faire l'objet d'un examen par le Service vétérinaire.
5. Le jugement du caractère dangereux d'un chien résulte de l'examen effectué par le Service vétérinaire.
6. Le détenteur d'un chien, dont l'animal est désigné par le Service vétérinaire comme devant subir un examen, a l'obligation d'y soumettre son animal.
7. Le Service vétérinaire détermine si l'animal doit être qualifié de dangereux pour l'homme et si son comportement est corrigible par une formation adéquate.
8. Si un chien est qualifié de dangereux par le Service vétérinaire, il doit être tenu en laisse et muni d'une muselière en dehors de la sphère privée.
9. Si le comportement du chien est jugé corrigible par le Service vétérinaire, le détenteur de l'animal doit immédiatement suivre des cours d'éducation canine appropriés. D'autres mesures peuvent être prises par le Service vétérinaire.
10. Si le comportement du chien est jugé incorrigible, le Service vétérinaire décide de son euthanasie.
11. Tous les frais d'examens et autres frais résultant de l'application de la présente disposition sont à la charge du détenteur de l'animal."
Se fondant sur l'art. 24b al. 2 LcLPA, le Conseil d'état du canton du Valais a édicté, le 7 décembre 2005, la liste suivante de races de chiens et leurs croisements dont la détention est interdite en Valais:
«Pitbull-Terrier, American Staffordshire-Terrier, Staffordshire-Bullterrier, Bullterrier, Dobermann, Dogue argentin, Fila Brasileiro, Rottweiler, Mastiff, Mâtin Espagnol, Mâtin Napolitain, Tosa».
Le 21 décembre 2005, le Conseil d'Etat, concrétisant l'art. 24b LcLPA, a adopté un arrêté dont la teneur est la suivante:
"1. Toute personne domiciliée en Valais, qui est en possession d'un chien dont la race figure sur la liste des chiens et de leurs croisements interdits sur territoire valaisan (ci-après liste des chiens interdits), a l'obligation de soumettre son animal, d'ici au 30 septembre 2006, à un examen qui sera effectué par le service vétérinaire. Selon le résultat de l'examen, soit le chien sera considéré comme potentiellement dangereux au sens de l'art. 24b al. 3 LcLPA, soit le propriétaire sera tenu de se séparer de son/ses chien/s.
2. Tout chien potentiellement dangereux, né avant le 1er mars 2006, recevra une autorisation exceptionnelle pour autant qu'il soit stérilisé.
3. Toute personne en possession d'un chien figurant sur la liste des chiens interdits et qui n'est pas muni d'une puce électronique doit annoncer son animal au service vétérinaire d'ici au 1er mars 2006.
4. Tout chien qui figure sur la liste des chiens interdits et qui n'est pas annoncé ou n'est pas muni d'une puce électronique après le 30 juin 2006 sera euthanasié.
5. Tout séjour en Valais de chiens figurant sur la liste des chiens interdits est autorisé pour une durée maximale de 30 jours et à condition que l'animal soit tenu en laisse et muni d'une muselière.
6. Le département compétent prépare, en collaboration avec les communes, une liste des chiens potentiellement dangereux autorisés par le service vétérinaire, avec le nom de leur propriétaire respectif. Les communes en permettent la consultation.
7. Le vétérinaire cantonal édicte une directive à l'intention des vétérinaires, les obligeant à annoncer au service vétérinaire tout nouveau chien figurant sur la liste des chiens interdits.
8. Le département compétent est chargé de l'application de la présente décision."
B. Le 23 janvier 2006, l'Association Canis et treize consorts ont formé un recours de droit public auprès du Tribunal fédéral pour violation des art. 8 al. 1, 9 et 10 al. 2 Cst. Ils concluent, en substance, à l'annulation de l'arrêté adopté le 21 décembre 2005 par le Conseil d'Etat du canton du Valais, y compris la liste des chiens interdits en Valais édictée le 7 décembre 2005. Le Conseil d'Etat conclut au rejet du recours. Lors du second échange d'écritures, les parties ont déclaré maintenir leurs conclusions initiales.
C. Par ordonnance du 9 mars 2006, le Président de la IIe Cour de droit public a en principe rejeté la requête d'effet suspensif. Il l'a uniquement admise en ce sens qu'il ne pourra être procédé à la stérilisation ou à l'euthanasie de chiens figurant sur la liste des chiens et de leurs croisements interdits, nés après le 1er mars 2006 et jugés corrigibles, qu'une fois la procédure fédérale close.

Le Tribunal fédéral considère en droit:
1. 1.1 L'acte attaqué a été édicté avant le 1er janvier 2007; la présente procédure reste donc régie par la loi fédérale d'organisation judiciaire du 16 décembre 1943 (OJ; cf. art. 132 al. 1 de la loi du 17 juin 2005 sur le Tribunal fédéral [LTF; RS 173.110]).
1.2 L'arrêté du Conseil d'Etat du 21 décembre 2005 (y compris la liste des chiens interdits) n'est pas susceptible d'être attaqué par un moyen de droit cantonal; par conséquent, seule la voie du recours de droit public au Tribunal fédéral est ouverte (art. 84 et 86 al. 1 OJ).
1.3 Les huit particuliers (recourants n° 7 à 14) qui recourent sont domiciliés en Valais ou y séjournent dans leur résidence secondaire et sont propriétaires de chiens (Rottweiler, Dogue argentin, Amstaff, Mastiff) figurant sur la liste des chiens interdits, dont la détention est désormais soumise à des restrictions; touchés dans leurs intérêts juridiquement protégés au sens de l'art. 88 OJ ils ont qualité pour recourir.
S'agissant des associations recourantes, leur qualité pour agir par la voie du recours de droit public suppose qu'elles aient la personnalité juridique et que la défense des intérêts de leurs membres figure parmi leurs buts statutaires. En outre, leurs membres, du moins la majorité ou un grand nombre d'entre eux, doivent être personnellement touchés par l'acte litigieux (<ref-ruling> consid. 1.2.1 p. 30 et les arrêts cités). C'est le cas de l'«Association Canis Valais-Romand» (recourante n° 1), constituée selon les <ref-law>, avec siège à Sion, qui a pour but statutaire de contester les restrictions prévues à l'art. 24b LcLPA et dont on peut admettre qu'un grand nombre de membres, directement ou virtuellement atteints par l'arrêté attaqué, sont domiciliés en Valais. Il en est également ainsi de l'«Association Molo's» (recourante n° 6), association romande dont un grand nombre de membres sont, selon toute vraisemblance, domiciliés en Valais. Les quatre organisations Dobermann-Club Suisse, American Staffordshire Terrier Club-Suisse, Old English Mastiff Club Schweiz, Club Suisse Du Molosse sont des associations (recourantes n° 2 à 5) d'importance nationale, dont la qualité pour recourir ne peut être reconnue en l'espèce, dès lors que l'on peut présumer - à défaut d'allégation contraire - que ni la majorité ni un grand nombre de leurs membres ne sont domiciliés dans le canton du Valais; leur recours de droit public est donc irrecevable.
1.4 L'arrêté entrepris a été publié le 21 décembre 2005, d'abord sous la forme d'un «communiqué pour les médias» ensuite dans le Bulletin officiel. Déposé le 23 janvier 2006, le présent recours respecte le délai de trente jours (art. 89 al. 1 OJ), compte tenu des féries judiciaires (art. 34 al. 1 let. c OJ).
1.5 La modification du 6 décembre 2002 de la LcLPA est entrée en vigueur le 1er janvier 2004. Les nouvelles dispositions sur lesquelles se fonde l'arrêté litigieux, singulièrement l'art. 24b al. 2 LcLPA, n'ont pas été contestées par la voie du recours de droit public dans le délai légal et ne font ainsi pas l'objet de la présente procédure fédérale. Le Tribunal fédéral ne peut procéder qu'à un examen préjudiciel de la constitutionnalité de l'art. 24b al. 2 LcLPA, ce qui signifie qu'en cas d'admission du recours seul l'arrêté du Conseil d'Etat, en tant qu'acte pris en application de cette norme, sera annulé (cf. <ref-ruling> consid. 6.1; arrêt 1P.254/2002 du 6 novembre 2002, consid. 1.2 non publié in <ref-ruling>).
2. Les recourants invoquent d'abord la violation de la liberté personnelle (art. 10 al. 2 Cst.). La question de savoir si et dans quelle mesure l'interdiction de détenir un chien tombe dans le champ d'application de ce droit fondamental comme élément indispensable à l'épanouissement de la personne humaine est demeurée indécise jusqu'à présent (<ref-ruling> consid. 3.2; arrêt 2P.221/2006 du 2 mars 2007, consid. 2). Il sied de préciser qu'en principe la détention de chiens appartenant à une race déterminée n'entre pas dans le champ d'application de la liberté personnelle. Une atteinte à ce droit fondamental pourrait, le cas échéant, être admise lorsque le détenteur d'un chien est obligé de se séparer de son animal avec lequel il entretient une relation affective étroite ou lorsqu'un passionné de chiens se voit interdire de manière générale la détention d'un chien. Tel n'est pas le cas en l'espèce. Les recourants ne font pas valoir que la réglementation attaquée les contraindrait (respectivement leurs membres concernés) à se séparer ou à euthanasier leurs chiens. Ils ne doivent pas non plus s'attendre à ce que de telles mesures, fondées sur ladite réglementation, soient adoptées si les chiens qu'ils détiennent déjà ont vraiment les caractéristiques mentionnées dans l'acte de recours. Certes, en cas d'acquisition d'un nouveau chien, les recourants seront limités aux races ne figurant pas sur la liste litigieuse, mais cette limitation du choix ne constitue pas à elle seule une atteinte à l'épanouissement indispensable de la personne humaine protégé par le droit fondamental à la liberté personnelle.
3. 3.1 Aux yeux des recourants, la réglementation attaquée, qui interdit la détention de chiens figurant sur la liste incriminée et qui prévoit comme mesure transitoire la stérilisation de ces animaux, violerait les principes de l'égalité et de la protection contre l'arbitraire. La délimitation prévue par la liste édictée ne reposerait sur aucune base scientifique. Par ailleurs, la réglementation choquerait le sens du droit d'équité. Ainsi, un citoyen domicilié dans le canton du Valais se verrait interdire la détention d'un chien figurant sur la liste des chiens interdits, alors que les ressortissants d'autres cantons pourraient séjourner en Valais avec de tels chiens. De plus, il serait difficile voire impossible d'identifier les croisements interdits. La réglementation entraînerait à maints égards des résultats contradictoires. Alors que la race Dobermann serait soumise à des mesures draconiennes, le Berger allemand ou le Saint-Bernard ne figureraient pas sur la liste. Une partie des chiens de race figurant sur la liste litigieuse n'aurait jamais été impliquée dans des accidents par morsures de chiens, répertoriés dans l'étude scientifique consacrée à ce sujet (voir Medizinisch versorgte Hundebissverletzungen in der Schweiz, Opfer-Hunde-Unfallsituationen, Ursula Horisberger, Thèse, Berne 2002). Selon cette étude, 90% des morsures nécessitant des soins médicaux seraient causées par des chiens qui ne sont ni des molosses, ni des chiens de combat. De 1995 à 2005, trois accidents mortels auraient été répertoriés (1999: décès d'une personne âgée des suites d'une morsure à la jambe survenue plusieurs semaines auparavant; 2000: décès par noyade d'une femme poursuivie par un chien; 2005: enfant mortellement blessé par une meute de chiens). Dans le canton du Valais, un Saint-Bernard, dont la race ne figure pas sur la liste incriminée, aurait été à l'origine du dernier accident mortel, survenu en 1937. Les recourants soutiennent encore que la liste des accidents mortels répertoriés en Allemagne de 1968 à 2005 ne se référerait à aucune des races interdites. Par ailleurs, il serait erroné d'assimiler les molosses et les chiens de combat. Enfin, la réglementation attaquée, fondée sur la LcLPA, ne reposerait pas sur une base légale suffisante, dès lors que la loi fédérale sur la protection des animaux aurait pour objectif prioritaire de protéger les animaux et non les hommes.
3.2 Dans la mesure où les recourants se plaignent de ce que la réglementation attaquée ne repose pas sur une base légale suffisante, leur grief doit être rejeté. La loi fédérale du 9 mars 1978 sur la protection des animaux (LPA; RS 455) tend exclusivement à la protection de ceux-ci, tout comme la LcLPA sur laquelle se fonde l'arrêté entrepris. Toutefois, compte tenu des dispositions sur la compétence fédérale en la matière (cf. art. 80 Cst.), rien n'empêche les cantons de prévoir des règles de police sur la détention des animaux visant à préserver la sécurité et l'ordre publics (cf. <ref-ruling>72 consid. 2 p. 174 et l'arrêt cité). Le canton du Valais a fait usage de cette faculté en édictant non pas une loi spéciale mais un arrêté d'exécution de la LPA, singulièrement les articles 24a ss LcLPA, dont la validité ne saurait ainsi être contestée. La question de savoir si l'art. 24b LcLPA constitue une base légale suffisante ne doit être examinée que sous l'angle de l'arbitraire, vu qu'en l'espèce la violation d'un droit fondamental spécifique n'est pas en cause. En édictant les dispositions attaquées, le Conseil d'Etat n'a manifestement pas outrepassé ses compétences.
3.3 Il convient d'examiner si le contenu de la réglementation attaquée est conforme aux art. 8 et 9 Cst.
Un arrêté de portée générale viole le principe de l'égalité ancré à l'art. 8 al. 1 Cst. - ainsi que le principe de la protection contre l'arbitraire (art. 9 Cst.) qui est étroitement lié à celui de l'égalité - lorsqu'il établit des distinctions juridiques qui ne se justifient par aucun motif raisonnable au regard de la situation de fait à réglementer ou lorsqu'il omet de faire des distinctions qui s'imposent au vu des circonstances, c'est-à-dire lorsque ce qui est semblable n'est pas traité de manière identique et ce qui est dissemblable ne l'est pas de manière différente. Il faut que le traitement différent ou semblable injustifié se rapporte à une situation de fait importante (<ref-ruling> consid. 4.2 p. 6-7, 394 consid. 4.2 p. 399). La question de savoir s'il existe un motif raisonnable pour une distinction peut recevoir des réponses différentes suivant les époques et les idées dominantes. Le législateur dispose toutefois d'un large pouvoir d'appréciation dans le cadre de ces principes et de l'interdiction de l'arbitraire (<ref-ruling> consid. 4.2 p. 7).
3.4 Dans la mesure où les recourants soutiennent que le principe de l'égalité serait violé parce que les ressortissants d'autres cantons seraient soumis à des règles moins strictes que celles qui sont applicables aux citoyens valaisans, leur grief tombe à faux. Le principe de l'égalité n'exclut pas que les cantons édictent des réglementations différentes dans le même domaine; cela résulte de la structure fédéraliste de la Suisse (<ref-ruling> consid. 6d p. 179 et les arrêts cités). L'exiguïté du territoire et la mobilité de la population peuvent expliquer les attentes de celle-ci quant à l'unification - du moins partielle - au niveau national des règles sur la détention des chiens; toutefois, d'après les règles fédérales actuelles sur la compétence, les cantons sont libres - dans les limites tracées par la Constitution fédérale - de régler cette question comme ils l'entendent (cf. art. 3 Cst.).
De même, ne constitue pas une violation du principe de l'égalité le fait que l'interdiction introduite par l'arrêté attaqué de détenir des chiens figurant sur la liste ne soit pas applicable aux personnes qui séjournent provisoirement, soit 30 jours au maximum dans le canton du Valais. Cette exception en faveur des détenteurs de chiens qui sont soumis à d'autres règles en raison de leur domicile en dehors du canton du Valais repose sur des motifs objectifs. Dès lors, la seule question qui se pose est celle de savoir si la réglementation contestée respecte les principes de l'égalité et de la protection contre l'arbitraire en ce qui concerne les détenteurs de chien domiciliés dans le canton du Valais.
4. 4.1 L'interdiction absolue de certaines races de chiens et de leurs croisements, fondée sur l'art. 24b al. 2 LcLPA, tend à protéger la population du risque de blessures graves par morsures. Toutefois, pour éviter de telles blessures, d'autres mesures sont envisageables (voir les recommandations du groupe de travail de l'Office vétérinaire fédéral relatives à la teneur des législations cantonales sur les chiens dangereux [état au 21 décembre 2000]). Ainsi, des mesures préventives peuvent d'abord viser la personne du détenteur, en soumettant l'autorisation de détenir des chiens potentiellement dangereux à des conditions particulières (aptitude personnelle, formation, conditions adéquates quant à l'espace, éventuellement preuve de l'utilisation du chien à des fins particulières, notamment dans les services de protection) et en instaurant l'obligation d'obtenir une telle autorisation. Par ailleurs, les mesures de protection peuvent porter sur la détention même des chiens, en imposant la laisse ou le port de la muselière à certaines catégories de chiens dans certains espaces délimités (lieux publics très fréquentés; cf. <ref-ruling>45 consid. 4.2 et 5 p.147 s.) ou en limitant la détention ainsi que la promenade simultanée de plusieurs chiens potentiellement dangereux (cf. <ref-ruling>72 consid. 3 p. 177). Une autre mesure préventive peut consister en l'obligation de soumettre des chiens potentiellement dangereux ou identifiés comme tels à un test de comportement déterminant pour obtenir une autorisation ou pour continuer à en bénéficier. De même, l'obligation d'annoncer les accidents par morsures, telle que prévue sur le plan fédéral par l'art. 34a al. 1 let. a - dans sa teneur du 12 avril 2006 - de l'ordonnance sur la protection des animaux (OPAn; RS 455.1) peut constituer un fondement pour des mesures de protection concrètes (cf. <ref-ruling>72 consid. 2 p. 175). Enfin, le danger potentiel émanant des chiens peut être réduit par des règles sur l'élevage et le commerce interdisant la poursuite de l'élevage de lignées de chiens agressifs ou l'importation de chiens de provenance invérifiable.
4.2 Si la nécessité de mesures de protection n'est pas contestée, il n'en va pas de même du genre et de l'ampleur de ces mesures, en raison notamment des intérêts divergents qui sont en cause. L'interdiction absolue de certaines races de chiens et de leurs croisements, édictée par le Conseil d'Etat du canton du Valais, pourrait apparaître comme étant excessive, compte tenu de la responsabilité incombant en principe aux détenteurs de chiens, d'une part, ainsi que de l'existence de toute une palette de mesures moins restrictives, d'autre part. Nonobstant l'absence de données statistiques fiables, il est toutefois avéré que des chiens (y compris ceux appartenant à certaines races) peuvent provoquer et ont provoqué des accidents (extrêmement) graves, qui ont affecté non seulement d'autres chiens mais encore et surtout des personnes (cf. <ref-ruling>72 consid. 3 p. 176 s.). De plus, certaines races de chiens sont susceptibles d'effrayer la population, créant ainsi un sentiment d'insécurité. En cas d'interdiction absolue de détenir certaines races de chiens réputés pour être agressifs et dangereux (molosses, chiens de combat) et de procéder à leurs croisements, l'intérêt des détenteurs ou acquéreurs potentiels s'oppose en principe à celui du public - en particulier à celui des enfants - pour lequel il est primordial d'éviter les risques que représentent des chiens (potentiellement) dangereux, c'est-à-dire les atteintes à la vie et à l'intégrité corporelle (art. 10 al. 1 et 2 respectivement art. 11 al. 1 Cst.). Cette disproportion manifeste des intérêts en présence permet de considérer que l'interdiction contestée, limitée à certaines races de chiens qui représentent 1,7% du parc canin valaisan, ne constitue pas une mesure déraisonnable, puisqu'elle a pour but de garantir la sécurité publique et la protection de la population; dès lors, elle ne viole pas les art. 8 et 9 Cst. Ainsi, le législateur cantonal pouvait, dans le cadre de son pouvoir d'appréciation, préférer l'interdiction pure et simple de certaines races de chiens et de leurs croisements - même si ces derniers ne sont pas toujours aisément identifiables - à l'instauration de mesures spécifiques dont le contrôle s'avère difficile à effectuer.
4.3 S'agissant plus précisément de la liste contestée, il sied d'abord de relever qu'en interdisant la détention de chiens de douze races, le canton du Valais a instauré la réglementation cantonale la plus restrictive à ce jour, d'autres cantons ne prévoyant qu'un régime d'autorisation pour la détention de chiens dangereux ou potentiellement dangereux (cf. notamment <ref-ruling> pour Bâle-Campagne et l'<ref-ruling>72 précité pour Genève). Cette diversité des réglementations cantonales témoigne du large pouvoir d'appréciation des cantons, compétents en la matière.
Plusieurs éléments peuvent entrer en ligne de compte lors de l'établissement d'une liste de chiens interdits. L'appartenance d'un chien à une certaine race n'est certes pas un critère exclusif pour le degré de sa dangerosité, le caractère de cet animal étant dans une grande mesure formé par son éducation (socialisation) et par les influences de son environnement (<ref-ruling> consid. 4.2 p. 11 et les références). Toutefois, les morsures de certaines races de chiens et de leurs croisements ont des conséquences particulièrement graves, dues notamment à la morphologie, à la force, à la façon d'attaquer ou au «seuil d'excitation» de l'animal. Par ailleurs, la liste valaisanne, sur laquelle figurent des races de chiens à problèmes, correspond quasiment à la liste édictée par l'Office vétérinaire fédéral, le 12 janvier 2006, comprenant treize races, qu'il était prévu de soumettre à autorisation (American Staffordshire Terrier, Bull-terrier, Chien de cour italien, Dobermann, Dogue argentin, Fila Brasileiro, Mastiff, Mâtin espagnol, Mâtin napolitain, Dogue des canaries, Rottweiler, Staffordshire Bull Terrier et Tosa) ainsi que les chiens de type pitbull, dont l'interdiction était prévue (cf. Mesures «Chiens dangereux», publication de l'Office vétérinaire fédéral, parue en janvier 2006). La liste valaisanne comprend également les huit races de chiens qui ont été soumises à autorisation dans le canton de Bâle-Campagne (<ref-ruling> précité). Même s'il faut reconnaître que la liste contestée est, en l'état, imparfaite, du fait que certaines races de chiens y figurent alors que leur dangerosité n'est scientifiquement pas avérée, ou que certaines races que l'on pourrait qualifier de dangereuses en raison de leur implication dans des accidents par morsures (le Berger allemand ou belge) n'y figurent pas, elle ne doit pas pour autant être annulée. Le législateur cantonal disposant d'un grand pouvoir d'appréciation, il lui était loisible d'écarter certains chiens de sa liste d'interdiction, en prenant également en considération d'autres critères, tel le symbole (bien culturel) que peut représenter une race de chiens (le Saint-Bernard) ou les habitudes de la population s'agissant de certaines races de chiens (le Berger allemand considéré comme chien policier). Enfin, il y a lieu de relever une certaine urgence à légiférer en la matière, ce qui explique que le législateur valaisan n'ait pas jugé opportun d'attendre la parution de données statistiques fiables, d'où le caractère provisoire de la liste contestée.
4.4 L'arrêté du Conseil d'Etat du 21 décembre 2005 contient des dispositions transitoires pour les détenteurs de chiens figurant sur la liste. Elles prévoient notamment la stérilisation de ces animaux lorsque l'examen obligatoire auquel ils sont soumis révèle qu'ils doivent être considérés comme potentiellement dangereux. Le Conseil d'Etat précise que l'obligation de stériliser constitue un corollaire nécessaire et logique à l'interdiction des races. Les recourants se bornent à évoquer cette question; à défaut de motivation suffisante au sens de l'art. 90 al. 1 let. b OJ (cf. <ref-ruling> consid. 1.3 p. 261 et l'arrêt cité), il n'y a pas lieu d'examiner la constitutionnalité de ces dispositions transitoires.
4.5 Force est de conclure que, pour l'essentiel, la réglementation édictée par le Conseil d'Etat du canton du Valais, fondée sur des critères qui n'apparaissent pas comme déraisonnables, n'a pas été établie en violation des principes de l'égalité et de la protection contre l'arbitraire.
5. Au vu de ce qui précède, le recours doit être rejeté, dans la mesure où il est recevable. Succombant, les recourants doivent supporter un émolument judiciaire, solidairement entre eux (art. 156 al. 1 et 7 OJ). Il n'ont pas droit à des dépens (art. 159 al. 1 OJ). Il n'y a pas lieu d'allouer des dépens au Conseil d'Etat (cf. art. 159 al. 2 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours de droit public est rejeté dans la mesure où il est recevable.
2. Un émolument judiciaire de 5'000 fr. est mis à la charge des recourants, solidairement entre eux.
3. Le présent arrêt est communiqué en copie au mandataire des recourants et au Conseil d'Etat du canton du Valais.
Lausanne, le 27 avril 2007
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière: