Faits:
A. Après un séjour irrégulier en Suisse dès 1990, X._, ressortissant de l'ex-Yougoslavie, né en 1961, a épousé le 12 février 1991 Y._, ressortissante suisse, née en 1945. Il a, de ce fait, obtenu une autorisation de séjour, régulièrement renouvelée jusqu'à l'obtention du permis d'établissement, en date du 21 mars 1996. Le 28 mai 1996, l'intéressé a obtenu la nationalité suisse par naturalisation facilitée en qualité de conjoint d'un ressortissant suisse sur la base de l'art. 27 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (LN; RS 141.0).
Depuis le début de son mariage, X._ a entretenu, au Kosovo, une liaison régulière avec une compatriote, A._, née en 1964, avec laquelle il a eu six enfants: B._, né en 1991, C._, née en 1993, D._, née en 1995, E._, née en 1998, F._, né en 2000 et G._, né en 2006, qui ont toujours vécu avec leur mère au Kosovo. Le 8 janvier 1999, X._, d'entente avec son épouse, a déposé en vain auprès de l'Office fédéral des réfugiés une demande de visa pour inviter en Suisse dix-neuf personnes de sa famille, dont sa compagne et ses quatre premiers enfants, qu'il a désignés comme sa belle-soeur et ses neveux et nièces.
Le couple X.Y._ s'est séparé à une date indéterminée, l'épouse ayant quitté le canton du Valais. Le divorce a été prononcé le 20 octobre 2005.
Le 17 mai 2006, X._ a épousé, au Kosovo, A._. Le lendemain, celle-ci a déposé une demande d'entrée et de séjour en Suisse pour rejoindre son mari et vivre auprès de lui avec leurs cinq enfants.
B. Par décision du 25 octobre 2007, le Service de l'état civil et des étrangers (actuellement le Service de la population et des migrations) du canton du Valais (ci-après: le Service cantonal) a rejeté la demande présentée par A.X._, B.X._, C.X._ et D.X._, celle des trois enfants cadets étant sans objet du fait de leur nationalité suisse. Ceux-ci étaient en effet nés après la naturalisation de leur père et, comme lui, avaient pu conserver leur nationalité en raison de l'écoule- ment du délai péremptoire de cinq ans de l'art. 41 LN permettant de faire annuler ces naturalisations. Le Service cantonal a considéré que X._ avait obtenu la naturalisation facilitée de manière frauduleuse, en dissimulant sa double vie et l'existence de ses enfants; son parcours démontrait que le but de son mariage avec une ressortissante suisse en 1991 était de lui permettre, à moyen terme, de s'assurer un statut en Suisse afin de se faire rejoindre ultérieurement par sa famille.
Le 7 janvier 2009, le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) a rejeté le recours déposé le 26 novembre 2007 par X._ contre la décision du Service cantonal du 25 octobre 2007.
C. Saisi d'un recours dirigé contre la décision rendue le 7 janvier 2009 par le Conseil d'Etat, le Tribunal cantonal du canton du Valais, Cour de droit public (ci-après: le Tribunal cantonal), l'a rejeté, par arrêt du 29 mai 2009. Il a retenu, en substance, que X._ ne pouvait pas, sans commettre un abus de droit, se prévaloir de sa nationalité suisse pour obtenir le regroupement familial en faveur de son épouse actuelle et de ses enfants, que le droit du conjoint étranger d'un ressortissant suisse d'obtenir, au sens de l'art. 7 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE), une autorisation de séjour, puis, après cinq ans, une autorisation d'établissement, ne constituait pas un droit absolu mais trouvait sa limite dans l'interdiction de l'abus de droit, que s'il n'avait pas caché la relation qu'il entretenait parallèlement à son mariage avec une compatriote et l'existence de ses enfants, X._ n'aurait obtenu ni une autorisation de séjour, ni une autorisation d'établissement, ni la nationalité suisse, et que l'intéressé ne pouvait pas invoquer les art. 17 al. 2 LSEE et 8 de la Convention européenne de sauvegarde des droits de l'homme et des libertés fondamentales du 4 novembre 1950 (CEDH; RS 0.101), compte tenu de l'âge de ses trois aînés, de leur méconnaissance de la langue française et de leurs importantes difficultés prévisibles d'adaptation et d'intégration en Suisse.
D. Par mémoire du 29 juin 2009, X._ demande au Tribunal fédéral de reconsidérer l'arrêt du Tribunal cantonal du 29 mai 2009, la décision du Conseil d'Etat du 12 janvier 2009, la décision du Service cantonal du 25 octobre 2007 et de donner un avis favorable relatif à l'entrée et au séjour en Suisse de son épouse et de ses enfants B._, C._ et D._. Il se plaint de la violation des art. 7 LSEE, 17 al. 2 LSEE et 8 CEDH.
Le Tribunal cantonal renonce à se déterminer. Le Conseil d'Etat se réfère à l'arrêt attaqué et conclut, sous suite de frais, au rejet du recours dans la mesure de sa recevabilité. L'Office fédéral des migrations conclut au rejet du recours dans la mesure où il est recevable.

Considérant en droit:
1. La loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) est entrée en vigueur le 1er janvier 2008. En vertu de l'art. 126 al. 1 LEtr, les demandes déposées avant l'entrée en vigueur de la loi sont régies par l'ancien droit. La demande d'autorisation de séjour déposée par A.X._ et ses enfants datant du 18 mai 2006, la présente affaire doit être examinée à la lumière de l'ancien droit.
2. Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 de la loi du 17 juin 2005 sur le Tribunal fédéral (LTF; RS 173.110). Il contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 96).
2.1 Le recourant n'a pas indiqué expressément par quelle voie de recours il voulait procéder au Tribunal fédéral. Toutefois, cette imprécision ne saurait lui nuire si son mémoire peut être considéré comme un recours remplissant les conditions de la voie de droit qui lui est ouverte (cf. <ref-ruling> consid. 1.2. p. 302 s.). Dès lors que le présent litige relève du droit public, seul le recours en matière de droit public est envisageable (cf. art. 82 ss LTF).
2.2 Selon l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. En vertu de l'art. 7 al. 1 LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour. Après un séjour régulier et ininterrompu de cinq ans, il a droit à l'autorisation d'établissement. Selon l'art. 17 al. 2 LSEE, applicable par analogie aux enfants étrangers d'un ressortissant suisse (<ref-ruling> consid. 1.2. p. 252 et la jurisprudence citée), les enfants célibataires âgés de moins de dix-huit ans d'un ressortissant étranger titulaire d'une autorisation d'établissement ont le droit d'être inclus dans l'autorisation de leurs parents aussi longtemps qu'ils vivent auprès d'eux. Pour juger de la recevabilité du recours en matière de droit public, seule est déterminante la question de savoir si un mariage au sens formel existe (cf. arrêt 2C_29/2009 du 29 mai 2009, consid. 2.1; <ref-ruling> consid. 1b p. 266) et si les enfants mineurs vivent en communauté avec leurs parents. En l'espèce, le recourant, marié, est ressortissant suisse, de sorte que son recours est recevable sous cet angle. La question de savoir si le refus d'octroi des autorisations de séjour sollicitées se justifie en raison d'un abus de droit ne concerne pas la recevabilité du recours, mais doit être examinée au fond (<ref-ruling> consid. 1b p. 266 et les références citées).
2.3 Selon l'art. 42 al. 1 LTF, le mémoire de recours doit indiquer les conclusions, les motifs et les moyens de preuve. En l'occurrence, le recourant a conclu à la reconsidération de l'arrêt du Tribunal cantonal du 29 mai 2009, la décision du Conseil d'Etat du 12 janvier 2009, la décision du Service cantonal du 25 octobre 2007, ce qu'il faut comprendre à la lecture de son mémoire comme une demande d'annulation ou de réforme, admissible au regard de l'art. 107 al. 2 LTF.
Le présent recours est en revanche irrecevable dans la mesure où le recourant conclut à l'annulation ou à la modification des décisions du Service cantonal et du Conseil d'Etat étant donné l'effet dévolutif du recours auprès du Tribunal cantonal (<ref-ruling> consid. 1 p. 441; <ref-ruling> consid. 1c p. 33).
2.4 Pour le reste, interjeté par une partie directement touchée par la décision attaquée et qui a un intérêt digne de protection à son annulation ou à sa modification (art. 89 al. 1 LTF), le recours est dirigé contre un jugement rendu par une autorité cantonale judiciaire supérieure de dernière instance (art. 86 al. 1 lettre d et al. 2 LTF). Déposé dans le délai (art. 100 al. 1 LTF) et la forme (art. 42 LTF) prévus par la loi, il est en principe recevable.
3. 3.1 Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'art. 106 al. 2 LTF. Il y procède en se fondant sur les faits constatés par l'autorité précédente (cf. art. 105 al. 1 LTF), à moins que ces faits n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (cf. art. 105 al. 2 LTF). Le recourant doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'art. 105 al. 2 LTF seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué (<ref-ruling> consid. 6.2 p. 288).
3.2 Le recourant fait valoir des faits qui ne ressortent pas de l'arrêt attaqué: Il souligne que la longue durée de son premier mariage démontre la solidité de cette union, en dépit de la relation hors mariage qu'il a entretenue, qu'il avait pendant toute la durée de son séjour en Suisse assumé la responsabilité principale de l'éducation de ses enfants qu'il rencontrait régulièrement au Kosovo et qu'il entretenait financièrement, que toutes les conditions pour l'accueil de sa famille étaient réunies et que l'adaptation de sa femme et de ses enfants en Valais serait aisée. Comme il n'expose pas concrètement, conformément aux exigences de l'art. 106 al. 2 LTF, en quoi l'arrêt attaqué est arbitraire à cet égard, ces faits sont irrecevables. Il n'est par conséquent pas possible de les prendre en considération et de s'écarter des faits retenus par l'arrêt cantonal.
4. Le recourant reproche au Tribunal cantonal d'avoir violé les art. 7 LSEE, 17 al. 2 LSEE et 8 CEDH garantissant le respect de la vie privée et familiale, dans la mesure où il a confirmé la décision refusant une autorisation de séjour à sa femme d'une part et à ses enfants d'autre part.
4.1 D'après l'art. 7 LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour (al. 1, 1ère phrase) puis, après un séjour régulier et ininterrompu de cinq ans, à l'autorisation d'établissement (al. 1, 2ème phrase), à moins que le mariage n'ait été contracté dans le but d'éluder les dispositions sur le séjour et l'établissement des étrangers (al. 2). Selon l'art. 17 al. 2 LSEE, applicable par analogie aux enfants étrangers d'un ressortissant suisse (<ref-ruling> consid. 1.2. p. 252 et la jurisprudence citée), les enfants célibataires âgés de moins de dix-huit ans d'un ressortissant étranger titulaire d'une autorisation d'établissement ont le droit d'être inclus dans l'autorisation de leurs parents aussi longtemps qu'ils vivent auprès d'eux. Enfin, l'art. 8 CEDH consacre le droit au respect de la vie privée et familiale (par. 1), tout en admettant qu'il puisse y avoir une ingérence dans son exercice à certaines conditions précises, notamment lorsqu'une telle mesure est nécessaire à la défense de l'ordre et à la prévention des infractions pénales (par. 2). Pour pouvoir invoquer la protection familiale découlant de l'art. 8 par. 1 CEDH, l'étranger doit entretenir une relation étroite et effective (<ref-ruling> consid. 5 p. 269; <ref-ruling> consid. 5.3.1 p. 211) avec une personne de sa famille ayant le droit de résider durablement en Suisse (sur cette notion, cf. <ref-ruling> consid. 1.3.1 p. 145 s.; <ref-ruling> consid. 3.1 p. 285).
D'après l'art. 10 al. 1 let. b LSEE enfin, l'étranger peut être expulsé de Suisse ou d'un canton si sa conduite, dans son ensemble, et ses actes, permettent de conclure qu'il ne veut pas s'adapter à l'ordre établi dans le pays qui lui offre l'hospitalité ou qu'il n'en est pas capable. Un étranger, dont le comportement est contraire à l'ordre public suisse, ne saurait se prévaloir de la nationalité suisse - ni d'ailleurs de l'autorisation d'établissement acquise frauduleusement - pour revendiquer une autorisation de séjour en faveur de la famille qu'il a fondée clandestinement dans son pays d'origine (cf. arrêt 2A.364/1999 du 6 janvier 2000, consid. 5d).
4.2 Les droits mentionnés par les art. 7 et 17 LSEE ainsi que 8 CEDH sont accordés sous réserve d'un abus de droit. Il y a abus de droit notamment lorsqu'une institution juridique est utilisée à l'encontre de son but pour réaliser des intérêts que cette institution juridique ne veut pas protéger (<ref-ruling> consid. 4 p. 101/102; <ref-ruling> consid. 5a p. 56; <ref-ruling> consid. 4 p. 103). Tel est le cas notamment lorsque le conjoint étranger invoque un mariage n'existant plus que formellement dans le seul but d'obtenir une autorisation de police des étrangers, car cet objectif n'est pas protégé par l'art. 7 al. 1 LSEE (<ref-ruling> consid. 4.2 p. 267 et la jurisprudence citée). L'existence d'un éventuel abus de droit doit être appréciée dans chaque cas particulier et avec retenue, seul l'abus manifeste pouvant être pris en considération.
4.3 En l'espèce, alors qu'il séjournait illégalement en Suisse, le recourant n'a pu obtenir une autorisation pour y séjourner qu'en épousant une ressortissante suisse d'origine hongroise, de seize ans son aînée. Dès le début du mariage, le recourant s'est rendu régulièrement au Kosovo, y a entretenu une liaison régulière et suivie avec son épouse actuelle. Le premier fils du recourant, B._, né en 1991, a été conçu peu avant le mariage du recourant avec Y._. La double vie conjugale du recourant a persisté pendant toute la durée du mariage. A aucun moment, le recourant et son épouse suissesse n'ont fait mention de l'existence des enfants vivant au Kosovo. En particulier, les questionnaires pour l'obtention du permis C, puis de la naturalisation facilitée, complétés par le recourant en 1996, ne contiennent aucun indication sous la rubrique réservée aux enfants du requérant. Cette dissimulation a atteint son point culminant lorsqu'en date du 8 juin 1999 le recourant et sa femme ont tenté d'accueillir en Valais les enfants B._, C._, D._ et E._, ainsi que leur mère, qu'ils ont présentés faussement comme des neveux et nièces du recourant, leur mère comme une belle-soeur. Ce n'est qu'à réception de la demande de regroupement familial du 18 mai 2006 que les autorités cantonales de police des étrangers ont été informées de l'existence des cinq enfants du recourant, nés entre 1991 et 2000.
Les circonstances du premier mariage, la double vie du recourant, la dissimulation constante de la naissance et de l'existence des enfants, ainsi que l'enchaînement des étapes de la vie conjugale du recourant permettent de conclure qu'il a abusé de l'institution du mariage avec une suissesse pour obtenir son autorisation d'établissement ainsi que la nationalité suisse.
A cela s'ajoute que depuis qu'il a épousé une ressortissante suisse et jusqu'au prononcé du divorce, le recourant a noué de front deux unions conjugales, l'une au Kosovo, l'autre en Valais. Une telle attitude est contraire à l'ordre public suisse et tombe sous le coup de l'art. 10 al. 1 lettre b LSEE. Si les autorités cantonales de police des étrangers avaient eu connaissance des circonstances réelles de la vie conjugale et familiale du recourant, elles ne lui auraient assurément pas accordé d'abord une autorisation de séjour, puis l'autorisation d'établissement. Pour les mêmes motifs, la demande de naturalisation facilitée aurait été refusée. Le droit des étrangers ne comportant pas - à l'inverse de la loi sur l'acquisition et la perte de la nationalité suisse - de limite temporelle à l'invocation de l'abus de droit, le fait que l'annulation de la nationalité suisse obtenue par la dissimulation de faits essentiels soit désormais exclue par l'écoulement du délai péremptoire de cinq ans prévu à cet effet par l'art. 41 LN, ne saurait être déterminant. La demande d'autorisation de séjour du 18 mai 2006 étant constitutive d'un abus de droit, il est superflu d'examiner si le regroupement familial sollicité est tardif ou non et s'il est plus motivé par des considérations de nature économique que par la volonté réelle de reconstituer la cellule familiale.
Par conséquent, c'est à bon droit que le Tribunal cantonal a refusé au recourant d'accorder une autorisation de séjour en Suisse à son épouse et ses enfants A._, B._ et C._.
5. Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable.
Succombant, le recourant doit supporter les frais judiciaires (art. 65 à 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au recourant, au Service de la population et des migrants, au Conseil d'Etat et à la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 21 janvier 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Dubey