Faits:
A. Le 29 juin 2005, le Conseil d'Etat du canton du Valais a adopté le règlement concernant le statut du personnel de la haute école pédagogique (ci-après: RpersHEP/VS ou encore le règlement sur le statut du personnel HEP; RSVS 419.103) en application de la loi valaisanne du 4 octobre 1996 concernant la haute école pédagogique (LHEP/VS ou encore loi sur la haute école pédagogique; RSVS 419.1) et de son ordonnance du 12 janvier 2000 concernant le statut du personnel de la haute école pédagogique (OpersHEP/VS ou encore ordonnance sur le statut du personnel HEP; RSVS 419.102), publié dans le Bulletin officiel du canton du Valais du 15 juillet 2005 (BO/VS 2005, n° 28, p. 1584 s.) pour entrer en vigueur le 1er septembre 2005.
Ce règlement comprend notamment les dispositions suivantes:
art. 4 traitement de professeur - traitement de chargé d'enseignement
1Le traitement servi aux enseignants de la HEP est fonction du temps et de la nature des tâches attribuées en qualité de professeur et de chargé d'enseignement.
2L'enseignant de la HEP reçoit un traitement de professeur uniquement pour la part de son activité consacrée aux tâches de recherche et développement en science de l'éducation, aux prestations à des tiers et, le cas échéant, à la conduite de dossiers de formation des praticiens-formateurs, de gestion des stages des étudiants, de gestion des examens finaux, de coordination des enseignements, de gestion des formations complémentaires, de responsabilité du système de qualité. La part d'activité affectée à ces tâches doit représenter au moins 10 pour cent du temps de travail.
3En plus des exigences arrêtées à l'alinéa précédent, l'intéressé doit remplir les conditions suivantes:
a) il doit être nommé pour au moins 50 pour cent d'un temps de travail annuel
b) il doit assumer pour au moins 8 pour cent de son temps de travail les tâches courantes d'enseignement.
4L'enseignant qui ne remplit pas les conditions fixées aux alinéas 2 et 3 reçoit un traitement de chargé d'enseignement.
B. Répondant à une mise au concours de "professeurs à la Haute école pédagogique du Valais (HEP-VS)" du 22 septembre 2000, A._, B._, C._, D._, E._ et F._ ont été nommés à titre provisoire au début de l'année 2001 en qualité de professeur à la Haute école pédagogique par le Conseil d'Etat du canton du Valais. Ils sont encore en fonction pour la période 2005/2006.
Par courrier du 5 juillet 2005, ils ont reçu du directeur de la HEP-VS le règlement du personnel HEP.
C. Agissant par la voie d'un recours de droit public déposé le 5 septembre 2005, A._, B._, C._, D._, E._ et F._ demandent au Tribunal fédéral, sous suite de frais et dépens, d'annuler le règlement sur le statut du personnel de la Haute école pédagogique du 29 juin 2005, plus particulièrement son art. 4. Ils invoquent la violation des art. 9 et 36 al. 2 et 3 Cst. ainsi que 57 Cst./VS.
Le Conseil d'Etat valaisan conclut au rejet du recours.
Lors d'un second échange d'écritures, les parties ont confirmé leurs conclusions respectives.
D. Par ordonnance du 13 avril 2005, le Président de la IIe Cour de droit public a rejeté la demande d'effet suspensif déposée par A._, B._, C._, D._, E._ et F._.

Le Tribunal fédéral considère en droit:
1. 1.1 Au regard de l'art. 84 OJ, la voie du recours de droit public n'est ouverte que si l'acte attaqué émane d'une autorité cantonale agissant en vertu de la puissance publique et qui affecte d'une façon quelconque la situation de l'individu, en lui imposant une obligation de faire, de s'abstenir ou de tolérer, ou qui règle d'une autre manière obligatoire ses rapports avec l'Etat, sous la forme d'un arrêté de portée générale, soit sous celle d'une décision particulière (cf. <ref-ruling> consid. 2a p. 174; <ref-ruling> consid. 3a p. 58 et les arrêts cités). En fixant le statut et la structure de rémunération des recourants, le règlement sur le statut du personnel HEP règle de manière obligatoire leurs rapports avec l'Etat du Valais. Il peut par conséquent faire l'objet d'un recours de droit public.
1.2 La législation valaisanne ne prévoyant aucune voie de droit cantonal permettant d'examiner in abstracto la constitutionnalité des arrêtés de portée générale, le présent recours respecte l'exigence de l'épuisement des moyens de droit cantonal au sens de l'art. 86 OJ.
1.3 Selon la jurisprudence relative à l'art. 88 OJ, la qualité pour former un recours de droit public contre un acte normatif cantonal appartient à toute personne dont les intérêts juridiquement protégés sont effectivement ou pourraient un jour être touchés par l'acte attaqué. Une simple atteinte virtuelle suffit, pourvu qu'il y ait un minimum de vraisemblance que le recourant puisse un jour se voir appliquer les dispositions prétendument inconstitutionnelles (<ref-ruling> consid. 1 p. 309, 26 consid. 1.2.1 p. 29-30 et la jurisprudence citée). En leur qualité d'enseignants remplissant les exigences personnelles et professionnelles pour exercer la fonction de professeurs au sein de la HEP-VS, les recourants sont touchés par chacune des dispositions du Règlement sur le statut du personnel HEP dont ils demandent expressément l'annulation. Ils ont donc qualité pour recourir. Le caractère provisoire ou définitif de leur nomination n'y change rien.
1.4 D'après l'art. 89 al. 1 OJ, l'acte de recours doit être déposé devant le Tribunal fédéral dans les trente jours dès la communication, selon le droit cantonal, de l'arrêté ou de la décision attaqués. Le règlement sur le statut du personnel HEP a été publié dans le Bulletin officiel du canton du Valais le 15 juillet 2005 (BO 28/2005, p. 1584 s.). Posté le 5 septembre 2005, le présent recours a donc été déposé en temps utile (cf. art. 34 al. 1 lettre b OJ).
1.5 A titre principal, les recourants demandent l'annulation du règlement sur le statut du personnel HEP dans son ensemble sans indiquer dans quelle mesure ils s'en prennent à chacune de ses dispositions. Ils ne démontrent pas non plus que l'annulation de telle ou telle disposition attaquée priverait le règlement de sens dans son ensemble. Insuffisamment motivée au regard de l'art. 90 al. 1 lettre b OJ, cette conclusion est irrecevable.
2. Appelé à statuer sur un recours de droit public dirigé contre un arrêté de portée générale, le Tribunal fédéral examine librement la conformité de cet arrêté au droit constitutionnel fédéral ou cantonal. Il n'annule toutefois les dispositions attaquées que si elles ne se prêtent à aucune interprétation conforme au droit constitutionnel ou si, en raison des circonstances, leur teneur fait craindre avec une certaine vraisemblance qu'elles ne soient interprétées de façon contraire à la Constitution (<ref-ruling> consid. 2; <ref-ruling> consid. 4, 348 consid. 1d). Dans la procédure dite de contrôle abstrait des normes, il est en effet rarement possible de prévoir d'emblée tous les effets de l'application d'un texte légal, même si, par sa précision, celui-ci n'offre guère de marge d'appréciation à l'autorité chargée de l'appliquer. Si une norme semble compatible avec la Constitution, au regard des circonstances ordinaires que le législateur devait considérer, le juge constitutionnel ne l'annulera pas pour le seul motif qu'on ne peut exclure absolument l'éventualité de son application inconstitutionnelle à des cas particuliers. Il ne le fera que si la perspective d'un contrôle concret ultérieur n'offre pas de garanties suffisantes aux destinataires de la norme litigieuse. Le rejet du grief d'inconstitutionnalité invoqué dans le cadre du contrôle abstrait d'une norme n'empêche en effet pas le recourant de soulever à nouveau ce grief contre la même disposition à l'occasion de son application à un cas d'espèce. L'arrêt rendu au terme de la procédure de contrôle abstrait ne bénéficie, dans cette mesure, que d'une autorité relative de la chose jugée. Le législateur n'en a pas moins pour devoir d'adopter une réglementation à même de prévenir, autant que possible, la violation ultérieure des droits fondamentaux. Il doit ainsi prendre en considération les conditions dans lesquelles la règle qu'il édicte sera appliquée et, en particulier, la qualité des organes chargés de cette application. Cela étant, le juge constitutionnel ne saurait laisser subsister une norme dont la teneur permet de craindre, avec une certaine vraisemblance et au vu des circonstances, qu'elle ne soit interprétée à l'avenir contrairement à la Constitution (ATF <ref-ruling> consid. 4 et les arrêts cités).
C'est à la lumière de ces principes qu'il convient d'examiner les griefs des recourants.
3. Les recourants se plaignent en premier lieu de la violation de l'art. 9 Cst. et de l'art. 57 Cst./VS. Ce faisant ils se plaignent implicitement d'une violation du principe de séparation des pouvoirs.
3.1 Le Tribunal fédéral reconnaît depuis toujours que le principe de la séparation des pouvoirs est garanti, au moins implicitement, par toutes les Constitutions cantonales et constitue un droit constitutionnel dont peut se prévaloir le citoyen. Ce principe garantit le respect des compétences établies par la Constitution. Il appartient en premier lieu au droit public cantonal de fixer les compétences des autorités. Le Tribunal fédéral examine librement l'interprétation des dispositions en matière de compétence qui figurent dans la Constitution cantonale et uniquement sous l'angle restreint de l'arbitraire celles qui figurent dans les lois cantonales (<ref-ruling> consid. 2c p. 116 et les nombreuses références citées).
3.2 L'art. 57 Cst./VS charge le Conseil d'Etat d'édicter sous forme de règlement les dispositions nécessaires à l'application des lois et décrets cantonaux (al. 1) et précise que la loi peut lui déléguer la compétence d'édicter des ordonnances en fixant leur but et les principes qui régissent leur contenu, la délégation devant toucher un domaine déterminé (al. 2).
3.3 L'art. 57 al. 1 Cst. fait référence à la notion d'ordonnance d'exécution par opposition à l'ordonnance dite de substitution. L'ordonnance d'exécution ne peut disposer qu'intra legem et non pas praeter legem. Elle peut établir des règles complémentaires de procédure, préciser et détailler certaines dispositions de la loi, éventuellement combler de véritables lacunes; mais à moins d'une délégation expresse, elle ne peut poser des règles nouvelles qui restreindraient les droits des administrés ou leur imposeraient des obligations, même si ces règles sont encore conformes au but de la loi (<ref-ruling> consid. 2.1 p. 97; <ref-ruling> consid. 5b, bb p. 287 et les références citées, André Grisel, Traité de droit administratif, tome I, Neuchâtel 1984, p. 82 s.).
4. Les recourants sont d'avis que l'art. 4 du règlement sur le statut du personnel HEP viole les dispositions de la loi sur la haute école pédagogique et celles de son ordonnance sur le statut du personnel HEP.
4.1 Le 4 octobre 1996, le Grand Conseil du canton du Valais a adopté la loi cantonale concernant la haute école pédagogique (HEP). Cette loi est entrée en vigueur le 1er juillet 1997. Son chapitre 7 règle les questions relatives au corps enseignant et au personnel technique et administratif. Selon l'art. 32 LHEP/VS, le corps enseignant, nommé par le Conseil d'Etat, comprend a) le directeur, b) les adjoints à la Direction, c) les professeurs et d) les chargés d'enseignement.
Les professeurs de la HEP doivent être porteurs de titres universitaires ou jugés équivalents, être au bénéfice d'une expérience pratique de l'enseignement et avoir acquis une qualification complémentaire en sciences de l'éducation (art. 35 al. 1 LHEP/VS). Leur engagement peut comprendre une part consacrée à l'enseignement et une part consacrée à la supervision des stages, à l'accompagnement de mémoires de fin d'étude, à l'encadrement pédagogique, à la formation continue des enseignants et à la recherche (art. 35 al. 2 LHEP/VS).
Selon l'art. 36 LHEP/VS, les droits et obligations du corps enseignant sont définis dans une ordonnance du Conseil d'Etat approuvée par le Grand Conseil et les traitements du corps enseignant sont arrêtés dans la loi du 17 novembre 1988 fixant le traitement du corps enseignant des écoles professionnelles supérieures et dans son ordonnance (RSVS 417.03). Selon le plan de classement de l'art. 20 de cette dernière loi, le traitement annuel auquel ont droit les professeurs HEP est fixé entre 90'233 fr. et 130'838 fr., (pour 2006: 103'914.85 fr. et 150'676.55 fr. en classe 45), tandis que celui des chargés d'enseignement est fixé entre 86'390 fr. et 125'266 fr. (pour 2006: 99'489.65 fr. et 144'260 fr. en classe 44).
4.2 Selon l'art. 3 OpersHEP/VS, est considéré comme professeur et nommé comme tel, l'enseignant qui a) remplit les conditions de qualifications exigées par la présente ordonnance et b) remplit le mandat défini à l'article 14 OpersHEP/VS, selon lequel les professeurs sont tenus de remplir les tâches prévues aux lettres A et C de l'article 13, remplissent d'ordinaire les tâches prévues à la lettre B et peuvent en outre être appelés à remplir les missions prévues à la lettre D. En revanche, l'enseignant est considéré comme chargé d'enseignement et nommé comme tel, lorsqu'il a) remplit les conditions de qualifications exigées par l'ordonnance et b) remplit les missions prévues à l'article 15 OpersHEP/VS, selon lequel il est tenu de remplir les tâches prévues à la lettre A de l'article 13 et peut en outre être appelé à remplir les tâches respectivement missions prévues aux lettres B et/ou D.
1.A) L'art. 13 OpersHEP/VS prévoit que, "les champs d'activités des professeurs et des chargés d'enseignement comportent:
A. les tâches courantes d'enseignement qui comprennent notamment:
a) l'enseignement ainsi que l'élaboration de cours;
b) la planification, la préparation, l'organisation et l'évaluation de l'enseignement;
c) la formation continue personnelle.
B. les tâches spéciales d'enseignement qui comprennent notamment:
a) l'accompagnement des travaux de mémoires de fin d'étude;
b) le suivi des stagiaires et l'animation pédagogique;
c) l'introduction à la profession;
d) la formation continue et complémentaire dans le champ scolaire.
C. les tâches de recherche appliquée en sciences humaines et de l'éducation (ci-après recherche), de développement et de prestations de service.
D. des missions particulières de type pédagogique, scientifique ou administratif, en particulier celle de responsable du domaine de la formation pratique de base ou du secteur des formations continues et complémentaires dans chacune des unités. "
4.3 L'art. 25 al. 1 et 2 OpersHEP/VS exige que les fractions de temps de travail liées aux divers champs d'activité des professeurs et des chargés d'enseignement soient mentionnées dans leur feuille de charge et laisse le soin à un règlement de préciser les détails notamment le coefficient qui permet de convertir les périodes hebdomadaires d'enseignement en heures de travail, le quota d'heures attribué par étudiant ou candidat pour le suivi des stagiaires, l'animation pédagogique, l'introduction à la profession, le suivi des travaux de mémoires de fin d'étude ainsi que pour la formation continue et complémentaire, le quota d'heures attribué pour la recherche et développement et les prestations de service et la durée des semestres. Ce même règlement précise les dispositions concernant les missions prévues à la lettre D. alinéa 1 de l'article 13 OpersHEP/VS, que la direction de la HEP doit répartir de manière équitable entre les professeurs et chargés d'enseignement (art. 25 al. 3 OpersHEP/VS).
5. En l'espèce, sous le titre marginal "traitement de professeur - traitement de chargé d'enseignement", l'art. 4 du règlement litigieux fait varier les traitements des professeurs et chargés de cours en fonction du temps et de la nature des tâches attribuées, de leur importance respective et proportionnelle ainsi que du taux et temps d'activité annuels des intéressés, les taux d'activité étant sujets à variation d'une année à l'autre (art. 5 du règlement). Dans ces conditions, un enseignant par hypothèse nommé professeur HEP parce qu'il remplit les conditions énoncées par l'art. 35 LHEP/VS et dont la décision de nomination mentionne notamment l'attribution du poste de professeur HEP en classe de traitement n° 45 (art. 7 OpersHEP/VS) peut, au gré des années et de l'organisation décidée par la Direction de la HEP, ne plus remplir les conditions qui, aux termes de l'art. 4 du règlement, lui conféreraient le droit à un traitement de professeur. A défaut, de remplir dites conditions, son traitement de professeur HEP est réduit à celui de chargé d'enseignement en classe 44 (art. 4 al. 4 du règlement). Le système mis en place par l'art. 4 du règlement attache par conséquent le titre de professeur ou de chargé de cours - et la rémunération qui y correspond - à des fractions d'activités et non plus à un poste. Les recourants s'en plaignent à bon droit. Cette conception ne trouve aucun fondement dans la LHEP/VS ni dans l'OpersHEP/VS, en particulier son art. 25. Il s'agit d'une inversion du système prévu par les art. 35 et 36 LHEP/VS.
En effet, l'art. 35 al. 1 LHEP/VS précise les qualifications requises par la loi pour prétendre au poste de professeur HEP. Les conditions étant remplies, les membres du corps enseignant sont nommés, la décision mentionnant notamment le poste attribué et le degré d'occupation, le cas échéant la possibilité de variation (art. 7 OpersHEP/VS). Ensuite, ces éléments étant décidés, le contenu de l'engagement peut varier et comprendre, conformément à l'art. 35 al. 2 LHEP/VS, une part consacrée à l'enseignement et une part consacrée à la supervision des stages, à l'accompagnement de mémoires de fin d'étude, à l'encadrement pédagogique, à la formation continue des enseignants et à la recherche. L'art. 25 OpersHEP/VS n'autorise nullement le Conseil d'Etat à modifier par voie réglementaire l'ordre légal, selon lequel c'est le fait d'être nommé au poste de professeur HEP qui définit les obligations à l'égard de l'employeur, notamment le contenu de l'engagement, et non pas un assortiment variable de fractions d'activités qui conditionne le poste auquel l'enseignant pourra prétendre.
Il en va de même en matière de traitement du corps enseignant. L'art. 36 al. 2 LHEP/VS dispose que la classe de traitement est fixée par l'art. 20 de la loi valaisanne du 17 novembre 1988 fixant le traitement du personnel des écoles de formation professionnelle supérieure. Une fois l'enseignant choisi pour occuper le poste de professeur HEP, la décision de nomination mentionne notamment le degré d'occupation, la classe de traitement et les éléments de calcul (art. 7 OpersHEP/VS). En aucune manière par conséquent, la classe de traitement des professeurs HEP n'est fonction des variations ou de fractions de temps d'occupation dans les divers champs d'activités qui leur incombent conformément à l'art. 35 al. 2 LHEP/VS. Le Conseil d'Etat n'est pas habilité à modifier par voie réglementaire l'ordre légal selon lequel le traitement dépend du poste et non pas des différentes fractions d'activités souverainement décidées chaque année par la Direction de la HEP. L'art. 35 al. 2 LHEP/VS n'accordant pas cette compétence au Conseil d'Etat, elle ne saurait a fortiori être déléguée à la Direction de la HEP en application de l'art. 25 OpersHEP/VS.
Fondé sur une interprétation arbitraire des art. 35 al. 2 LHEP/VS et 25 OpersHEP/VS, l'art. 4 du règlement concernant le statut du personnel de la Haute école pédagogique viole par conséquent le principe de la séparation des pouvoirs.
Également invoqué à l'appui de la conclusion d'annulation du règlement litigieux, le grief de violation de l'art. 36 Cst. - relatif à la "restriction des droits fondamentaux" - ne trouve en revanche pas d'application, lorsqu'est invoqué le droit constitutionnel à la séparation des pouvoirs.
Il résulte de ce qui précède que le recours doit être admis dans la mesure où il est recevable. L'art. 4 du règlement concernant le statut du personnel de la Haute école pédagogique est annulé.
Le canton du Valais, dont l'intérêt pécuniaire est en cause, doit supporter l'émolument judiciaire (art. 156 al. 2 OJ). Obtenant de cause avec l'aide d'un mandataire professionnel, les recourants ont droit à des dépens (art. 159 al. 1 et 3 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure ou il est recevable.
2. L'art. 4 du règlement concernant le statut du personnel de la Haute école pédagogique est annulé.
3. Un émolument de justice de 3'000 fr. est mis à charge du canton du Valais.
4. Une indemnité à titre de dépens de 3'000 fr. est allouée aux recourants à charge du canton du Valais.
5. Le présent arrêt est communiqué en copie au mandataire des recourants et au Conseil d'Etat du canton du Valais.
Lausanne, le 4 avril 2006
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le président: Le greffier: