Faits: A. Le 13 mars 2008, le Conseil communal d'Evolène a engagé la procédure de remembrement parcellaire urbain (RPU) du secteur "La Fauchère". En séance du 17 mars 2010, le Conseil d'Etat du canton du Valais a approuvé le périmètre provisoire du RPU défini par le conseil communal. Selon le rapport sur la procédure de remembrement établi par le bureau d'ingénieur mandaté par l'autorité communale (ci-après: rapport RPU), le secteur à remembrer correspond à une vaste aire située en zone d'habitation collective (indice de densité 0.6); ce secteur est composé de 86 parcelles et concerne 75 propriétaires. Le remembrement est motivé par le fait qu'une grande partie de la zone n'est pas équipée et que la forme des parcelles existantes - avec des "marteaux" pour la partie droite du secteur et des parcelles étroites pour la partie centrale - est peu propice à la construction et à l'utilisation rationnelle du sol. Le Conseil communal a par décision publiée au Bulletin officiel le 22 octobre 2010 introduit formellement la procédure de remembrement d'office du secteur La Fauchère. Sept personnes, dont A._ et B._ - propriétaires des parcelles n° 1070 et 1072 comprises dans le périmètre du RPU du secteur "La Fauchère" -, ont fait recours contre la fixation de ce périmètre auprès de la Commission de recours en matière agricole et de remaniements parcellaires (ci-après: la Commission de recours). A._ et B._ demandaient que leurs parcelles soient exclues de la zone à remembrer. Le Conseil communal s'est déterminé sur ces recours en approuvant, en séance du 24 février 2011, le procès-verbal de la commission Tourisme, Urbanisme, Jeunesse et Sport du 23 février 2011 qui proposait des réponses aux différents recours déposés. Selon ce document, la parcelle n° 1020 était indispensable à la reprise de la route existante, la procédure d'expropriation n'ayant pas été menée à terme en 1976; la parcelle n° 1072 - utilisée comme jardin de la parcelle n° 1070 -, était impropre à la construction et ne permettait pas de rationaliser les parcelles à bâtir en aval de la chaussée où subsistait un solde du bien-fonds n° 1079. La Commission de recours a procédé à une inspection locale le 7 juillet 2011 en présence notamment des recourants, du président de la Commune d'Evolène et de l'ingénieur du bureau ayant préparé le rapport RPU. Lors de l'inspection locale, le contenu du rapport de la Commission Tourisme, Urbanisme, Jeunesse et Sport du 23 février 2011 a été développé avec chacun des recourants et le Président de la Commune. Ce dernier a en particulier souligné que la problématique de la route d'accès serait régularisée avec le remembrement, précisant que cette route - qui ne permettait l'accès qu'à une petite partie du secteur actuellement - était toujours en mains privées; la procédure d'expropriation entreprise en 1976 n'avait pas été menée à terme; si la commune entretenait cette route, elle souhaitait néanmoins que la situation soit régularisée. B. Par décision du 7 juillet 2011, la Commission de recours a rejeté le recours formé par A._ et B._. Elle a estimé que les bien-fonds litigieux devaient être inclus dans le remembrement. La parcelle n° 1072 est, en raison de sa taille et de sa forme très étroite, manifestement impropre à la construction, de sorte qu'elle devait être comprise dans le périmètre litigieux. Quant à la parcelle n° 1070, elle devait être incluse dans le RPU pour des raisons de cohérence du périmètre et de raccordement aux eaux superficielles; en outre, la desserte à la parcelle serait améliorée et sécurisée par les travaux de la commune. C. Par acte du 14 décembre 2011, A._ et B._ forment un recours en matière de droit public par lequel ils concluent principalement à la nullité de la décision du 7 juillet 2011, subsidiairement à son annulation. Ils requièrent en particulier une procédure séparée pour la construction de la desserte routière (via une expropriation formelle) et l'équipement du secteur La Fauchère. Ils se plaignent pour l'essentiel d'une violation de leur droit de consulter le dossier, de la composition irrégulière de l'instance précédente, d'une constatation incomplète des faits, ainsi que de diverses violations du droit cantonal et fédéral. La Commission de recours conclut au rejet du recours. La Commune a déposé des observations tardives. Les recourants ont répliqué et confirmé leurs conclusions.