Faits:
A. Ressortissant kosovar, X._ est entré illégalement en Suisse le 3 novembre 1995 et y a déposé une demande d'asile qui a été rejetée le 2 avril 1996. Il a épousé, le 21 mars 1997, une Suissesse, D._, et a bénéficié, au titre du regroupement familial, d'une autorisation de séjour qui a été régulièrement prolongée. Le 4 juin 2002, il a obtenu une autorisation d'établissement. Le 26 février 2003, il s'est vu accorder la naturalisation facilitée qu'il avait sollicitée en mars 2002.
Le 24 mars 2004, les époux X.D._ ont introduit une requête commune en divorce; leur divorce, prononcé le 3 janvier 2005, est devenu définitif et exécutoire le 25 janvier 2005. Le 23 mars 2005, X._ a épousé au Kosovo une compatriote, Y._, qui lui avait donné une fille, A._, le *** 2004. Arrivée illégalement en Suisse avec sa fille le 2 juillet 2006, Y._ a obtenu une autorisation de séjour le 15 mars 2007. Les époux X.Y._ ont eu une deuxième fille, B._, le *** 2007.
Le 14 septembre 2007, l'Office fédéral des migrations (ci-après: l'Office fédéral) a annulé la naturalisation facilitée de X._. Le 24 juillet 2008, le Tribunal administratif fédéral a rejeté le recours interjeté contre la décision précitée.
Le *** 2009, les époux X.Y._ ont eu une troisième fille, C._.
Par lettre du 7 avril 2009, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a fait savoir à X._ qu'en cas d'annulation de la naturalisation, l'étranger n'était pas automatiquement réintégré dans son ancienne autorisation, mais que l'autorité compétente devait statuer sur les nouvelles conditions de séjour en Suisse. Il a donc demandé à l'intéressé d'apporter des preuves de sa bonne intégration.
Par décision du 4 juin 2009, le Service des migrations a refusé d'accorder une autorisation d'établissement, respectivement de séjour, à X._ et à ses trois filles ainsi que de prolonger l'autorisation de séjour de Y._; il a également fixé un délai de départ à la famille. Il a retenu que X._ avait commis un abus de droit en invoquant un mariage n'existant plus que formellement déjà lorsqu'il avait obtenu son autorisation d'établissement en 2002. Par conséquent, l'intéressé n'avait plus droit à une autorisation d'établissement ni même à une autorisation de séjour. En outre, il a souligné l'absence d'intégration professionnelle et sociale de X._ et l'importante dette sociale de la famille. Au surplus, l'intéressé s'était rendu fréquemment dans sa patrie et en parlait la langue. Sa femme, qui vivait en Suisse depuis moins de trois ans et n'avait aucun emploi, ne pouvait pas se prévaloir d'une bonne intégration. Quant aux trois filles, elles ne seraient pas déracinées par un départ pour le Kosovo, vu qu'elles étaient âgées seulement de quatre ans et demi, deux ans et quelques mois.
B. Par décision du 13 janvier 2010, le Département de l'économie du canton de Neuchâtel (ci-après: le Département de l'économie) a rejeté le recours de X._ et Y._ contre la décision du Service des migrations du 4 juin 2009, dont il a repris l'argumentation.
C. Par arrêt du 17 novembre 2010, la Cour de droit public du Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté le recours de X._ et Y._ contre la décision du Département de l'économie du 13 janvier 2010 et transmis le dossier au Service des migrations pour fixation d'un nouveau délai de départ. Il a retenu qu'au moment de l'octroi de l'autorisation d'établissement, le premier mariage de X._ était vidé de sa substance et que l'intéressé avait dissimulé aux autorités un élément essentiel propre à fonder la révocation de ladite autorisation. Il a considéré que les liens personnels et socioprofessionnels de l'intéressé avec la Suisse n'avaient rien d'exceptionnel, de sorte que sa situation personnelle ne s'opposait pas à la révocation de son autorisation d'établissement. En outre, la famille X.Y._ ne remplissait pas les conditions d'un cas individuel d'extrême gravité.
D. Agissant pour eux-mêmes et pour leurs trois filles, X._ et Y._ ont déposé au Tribunal fédéral un "recours en matière de droit public et recours constitutionnel subsidiaire" contre l'arrêt du Tribunal administratif du 17 novembre 2010. Ils concluent, sous suite de frais et dépens, à l'annulation de l'arrêt attaqué. Ils se plaignent en substance de constatation manifestement inexacte des faits et de violation du droit fédéral.
Le Tribunal administratif conclut au rejet du recours. Au nom du Département de l'économie, le Service juridique du canton de Neuchâtel conclut au rejet du recours dans le mesure où il est recevable. Le Service des migrations conclut au rejet du recours, sous suite de frais.
L'Office fédéral propose de rejeter le recours.
E. Par ordonnance du 13 janvier 2011, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif contenue dans le recours.
Considérant en droit:
1. La procédure destinée à régler les conditions de séjour des recourants a été initiée le 7 avril 2009, soit après l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20). C'est donc le nouveau droit qui est applicable en l'espèce (cf. art. 126 al. 1 LEtr a contrario; arrêt 2C_853/2010 du 22 mars 2011 consid. 1).
2. Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF). Il contrôle librement la recevabilité des recours qui lui sont soumis (ATF 136 I 42 consid. 1 p. 43 et la jurisprudence citée).
2.1 D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit.
On peut se demander si le présent litige porte sur la révocation d'une autorisation d'établissement octroyée à X._ ou sur le refus de lui accorder une autorisation de police des étrangers ainsi que, quelle que soit la réponse à cette question, sur les incidences du statut de celui-ci sur ceux de sa femme et de ses enfants (cf. ATF 135 II 1 consid. 1.2 p. 4). De toute façon, le recours apparaît recevable au regard de l'art. 83 let. c ch. 2 LTF pour les raisons qui suivent.
2.1.1 Selon la jurisprudence, le recours en matière de droit public est recevable à l'encontre des décisions prononçant la révocation d'une autorisation d'établissement ou en en constatant l'extinction, parce qu'il existe en principe un droit au maintien d'une telle autorisation (ATF 135 II 1 consid. 1.2.1 p. 4).
2.1.2 Par ailleurs, si l'on considère que le litige porte sur le refus d'une nouvelle autorisation de police des étrangers, on constate que le conjoint d'un ressortissant suisse a droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité à condition de vivre en ménage commun avec lui et qu'après un séjour légal ininterrompu de cinq ans, il a droit à l'octroi d'une autorisation d'établissement (art. 42 al. 1 et 3 LEtr). Or, le recourant a été marié initialement pendant plus de cinq ans à une Suissesse avec qui il cohabitait.
2.1.3 En outre, pour ce qui est de la famille de X._, on rappellera que, selon l'art. 43 al. 1 LEtr, le conjoint étranger du titulaire d'une autorisation d'établissement ainsi que ses enfants célibataires étrangers de moins de dix-huit ans ont droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité, à condition de vivre en ménage commun avec lui. Ces exigences sont satisfaites en l'occurrence.
2.2 Pour le surplus, le recours est dirigé contre une décision finale (art. 90 LTF) rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF); en outre, il a été déposé en temps utile (art. 100 al. 1 et 46 al. 1 let. c LTF) et dans les formes prescrites (art. 42 LTF) par les destinataires de l'arrêt attaqué qui ont un intérêt digne de protection à son annulation ou à sa modification (art. 89 al. 1 LTF). Par conséquent, il est recevable en tant que recours en matière de droit public et irrecevable comme recours constitutionnel subsidiaire (art. 113 LTF).
3. 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), en particulier en violation de l'interdiction de l'arbitraire (ATF 136 II 447 consid. 2.1 p. 450). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. art. 97 al. 1 LTF), il 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. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué (ATF 136 II 101 consid. 3 p. 104; 135 II 313 consid. 5.2.2 p. 322). En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (ATF 136 II 101 consid. 3 p. 104 s.; 135 II 313 consid. 5.2.2 p. 322).
Les recourants se plaignent d'une constatation manifestement inexacte des faits. En réalité, ils présentent leur propre version des faits, l'opposant à celle du Tribunal administratif qu'ils discutent comme s'ils intervenaient dans le cadre d'une procédure d'appel. Une telle argumentation ne permet toutefois pas au Tribunal fédéral de rectifier ou de compléter les constatations de fait de l'arrêt attaqué qui, au surplus, n'apparaissent pas avoir été établies par l'autorité précédente de façon manifestement inexacte ou en violation du droit (cf. art. 105 al. 2 LTF). De plus, les recourants se prévalent de faits non pertinents ayant trait notamment à la procédure d'annulation de la naturalisation, qu'il n'y a pas lieu de prendre en considération. C'est donc sur la base des faits retenus dans l'arrêt entrepris qu'il convient de vérifier si le droit fédéral a été correctement appliqué. Les critiques des recourants qui se fondent sur un état de fait différent de celui qui a été retenu par les juges cantonaux sont ainsi irrecevables.
4. 4.1 Dans un arrêt récent (ATF 135 II 1 consid. 3.7 et 3.8 p. 8 s.), le Tribunal fédéral a déclaré que l'étranger ne devait pas se trouver, à la suite de l'annulation de sa naturalisation, dans une situation moins favorable que celle dont il bénéficiait avant sa naturalisation et qu'il aurait conservée s'il n'avait pas été naturalisé. Il a donc estimé qu'il fallait lui reconnaître le statut qu'il avait avant la naturalisation pour autant qu'il n'y eût aucun motif d'extinction ou de révocation de l'autorisation qui lui avait été octroyée.
4. 4.1 Dans un arrêt récent (ATF 135 II 1 consid. 3.7 et 3.8 p. 8 s.), le Tribunal fédéral a déclaré que l'étranger ne devait pas se trouver, à la suite de l'annulation de sa naturalisation, dans une situation moins favorable que celle dont il bénéficiait avant sa naturalisation et qu'il aurait conservée s'il n'avait pas été naturalisé. Il a donc estimé qu'il fallait lui reconnaître le statut qu'il avait avant la naturalisation pour autant qu'il n'y eût aucun motif d'extinction ou de révocation de l'autorisation qui lui avait été octroyée.
4.2 4.2.1 L'art. 63 al. 1 LEtr énumère exhaustivement les hypothèses dans lesquelles une autorisation d'établissement peut être révoquée. Tel est en particulier le cas si l'étranger ou son représentant légal a fait de fausses déclarations ou a dissimulé des faits essentiels durant la procédure d'autorisation d'après l'art. 62 let. a LEtr applicable par renvoi de l'art. 63 al. 1 let. a LEtr.
Ce motif de révocation doit, d'une manière générale, être appliqué conformément à la pratique développée sous l'empire de l'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113; cf. arrêts 2C_837/2009 du 27 mai 2010 consid. 2 et 2C_651/2009 du 1er mars 2010 consid. 4.1.1). Sont ainsi essentiels, au sens de l'art. 62 let. a LEtr, non seulement les faits au sujet desquels l'autorité administrative pose expressément des questions à l'étranger durant la procédure, mais encore ceux dont l'intéressé doit savoir qu'ils sont déterminants pour l'octroi de l'autorisation (cf. arrêt 2C_60/2008 du 9 juin 2008 consid. 2.2.1). Le silence - ou l'information erronée - doit avoir été utilisé de manière intentionnelle, à savoir dans l'optique d'obtenir une autorisation de police des étrangers (arrêts 2C_837/2009 du 27 mai 2010 consid. 2 et 2C_651/2009 du 1er mars 2010 consid. 4.1.1). L'étranger est tenu d'informer l'autorité compétente de manière complète et conforme à la vérité sur tous les faits déterminants pour l'octroi de l'autorisation; il doit en particulier indiquer si la communauté conjugale n'est plus effectivement vécue (cf. arrêts 2A.455/2005 du 2 septembre 2005 consid. 2.1 et 2A.199/2005 du 13 avril 2005 consid. 2.1). Il importe peu que ladite autorité eût pu découvrir de tels faits par elle-même, si elle avait fait preuve de diligence (arrêts 2C_651/2009 du 1er mars 2010 consid. 4.1.1 et 2C_744/2008 du 24 novembre 2008 consid. 5.1). Même lorsque les conditions d'une révocation sont remplies, l'autorité compétente n'est pas tenue de prononcer cette mesure (l'autorisation "peut" être révoquée); elle doit examiner les circonstances du cas particulier et dispose d'une certaine marge d'appréciation (cf. ATF 112 Ib 473 consid. 4 p. 478; arrêt 2C_744/2008 du 24 novembre 2008 consid. 5.1).
4.2.2 Le recourant soutient qu'il peut se prévaloir de l'art. 63 al. 2 LEtr selon lequel l'autorisation d'établissement d'un étranger qui séjourne en Suisse légalement et sans interruption depuis plus de quinze ans ne peut être révoquée que pour les motifs mentionnés à l'art. 63 al. 1 let. b LEtr et à l'art. 62 let. b LEtr.
On ne saurait le suivre. Selon la jurisprudence (ATF 137 II 10 consid. 4.2 p. 12), ce délai de quinze ans doit être échu au moment où tombe la décision de révocation prise par l'autorité inférieure de police des étrangers. En l'occurrence, il aurait donc fallu que l'exigence d'un séjour légal et ininterrompu (sur cette notion, cf. ATF 137 II 10 consid. 4.6 p. 15 s.) de quinze ans fût satisfaite le 4 juin 2009, lorsque le Service des migrations a pris la décision qui est à l'origine du présent litige. Tel n'était pas le cas. Par conséquent, l'intéressé ne remplit pas les conditions d'application de l'art. 63 al. 2 LEtr.
5. Il convient d'examiner si, au moment de l'octroi de l'autorisation d'établissement, soit le 4 juin 2002, l'union conjugale de X._ et de son épouse suisse était réelle ou si cette communauté conjugale n'était plus effectivement vécue et que l'intéressé ait alors caché cet élément aux autorités pour obtenir ladite autorisation.
Se référant à une audition de l'épouse suisse du 30 janvier 2007, le Tribunal administratif a retenu que X._ avait proposé le mariage à D._, qu'il avait rassemblé tous les documents nécessaires à cet effet avant même qu'elle eût donné sa réponse et que le mariage avait été célébré environ six mois après la première rencontre. Selon D._, le couple avait commencé à avoir des problèmes vers 2000 ou 2001 et le mari avait radicalement changé après avoir obtenu une autorisation d'établissement. D._ a affirmé que les époux n'étaient jamais partis en vacances ensemble et qu'elle n'était pas allée dans la patrie de son mari, alors que celui-ci s'y rendait une à deux fois par an pour un long séjour (un mois et demi). Elle a ajouté que les époux partageaient très peu d'activités communes et que son mari n'avait pas voulu avoir d'enfants. Les juges cantonaux se sont aussi fondés sur les déclarations que Y._ a faites à la police le 10 juillet 2006. Selon ses dires, elle avait rencontré X._ au Kosovo en 2002, ils s'étaient fréquentés et elle était tombée enceinte. Depuis lors, le recourant avait prétendu que leur rencontre remontait seulement à fin 2003.
Le Tribunal administratif a déduit de ces éléments que la communauté conjugale de X._ et de sa première femme, D._, était superficielle et inconsistante. Il a relevé la rapidité avec laquelle les événements s'étaient enchaînés: mariage avec une Suissesse peu de temps après leur rencontre, qui faisait suite au rejet d'une demande d'asile, dépôt d'une demande de naturalisation avant même d'avoir obtenu une autorisation d'établissement, conception d'un enfant adultérin avec une compatriote moins d'un an après la naturalisation, introduction quasi immédiate d'une procédure de divorce et prompt remariage avec une étrangère. Les juges cantonaux ont vu dans cet enchaînement des faits un faisceau d'indices permettant de douter de l'authenticité de la relation conjugale du côté de X._. Au regard de l'ensemble des circonstances, c'est à juste titre que le Tribunal administratif a estimé que la relation des époux X.D._ était déjà vidée de sa substance lorsque le recourant s'était vu octroyer une autorisation d'établissement en juin 2002 et que celui-ci avait ainsi dissimulé aux autorités un élément essentiel propre à justifier la révocation de ladite autorisation. Les juges cantonaux n'ont donc pas violé le droit fédéral en considérant que le cas du recourant entrait dans le champ d'application de l'art. 62 let. a LEtr, par renvoi de l'art. 63 al. 1 let. a LEtr.
Certes, le recourant fait valoir que la succession des événements relatés ci-dessus tient aux aléas de la vie. On ne saurait le suivre, car on n'a pas affaire à un fait isolé, mais à un faisceau d'indices démontrant tous l'absence de communauté conjugale en tout cas depuis juin 2002.
6. Reste à examiner si le Tribunal administratif a fait bon usage de son pouvoir d'appréciation et respecté le principe de la proportionnalité en rendant l'arrêt attaqué.
6. Reste à examiner si le Tribunal administratif a fait bon usage de son pouvoir d'appréciation et respecté le principe de la proportionnalité en rendant l'arrêt attaqué.
6.1 6.1.1 Le Tribunal administratif a retenu que le recourant vivait en Suisse depuis 1995, ce qui n'était pas négligeable. Il faut cependant relativiser la durée de ce séjour, car l'intéressé est régulièrement retourné dans sa patrie pour de longues périodes (plus d'un mois).
Il ressort aussi de l'arrêt entrepris que le recourant a travaillé dans le bâtiment jusqu'en 2006 et qu'il a retrouvé un travail depuis le 1er mai 2009, peu après que le Service des migrations lui eût demandé de fournir des preuves de sa bonne intégration. Entre-temps, il avait bénéficié avec sa famille de l'aide sociale pour un montant dépassant 70'000 fr. En outre, il avait des actes de défaut de biens pour environ 95'000 fr. couvrant la période d'avril 2004 à avril 2009. Il avait produit un certificat portant seulement sur deux jours de travail ainsi que plusieurs courriers adressés à ses créanciers en vue de régulariser sa situation financière, au moment précisément où il devait démontrer sa bonne intégration (printemps 2009). Sur la base de ces éléments, les juges cantonaux ont considéré que l'intéressé n'avait pas réussi à s'intégrer dans le monde professionnel et économique.
Le Tribunal administratif a encore souligné que le recourant n'avait apporté aucune preuve de son intégration sociale et qu'il n'avait pas allégué de problème de santé. En outre, les juges cantonaux ont retenu que le recourant avait passé sa jeunesse dans sa patrie jusqu'à vingt-quatre ans et qu'il y était retourné régulièrement depuis qu'il vivait en Suisse, de sorte que sa réintégration dans son pays ne serait pas trop problématique.
Pour ce qui est de Y._, le Tribunal administratif a relevé qu'elle était entrée illégalement en Suisse où elle n'avait jamais travaillé, qu'elle n'avait pas démontré s'être bien intégrée socialement et qu'elle n'avait allégué aucun problème de santé. Il a estimé qu'elle pourrait sans difficulté refaire sa vie dans sa patrie où elle avait vécu jusqu'en 2006.
En ce qui concerne les trois filles des recourants, les juges cantonaux ont souligné que seule l'aînée pouvait avoir commencé l'école obligatoire et que, vu leurs âges - un an et demi à six ans environ au moment où l'arrêt attaqué est intervenu -, elles dépendaient encore beaucoup de leurs parents, de sorte qu'un départ pour leur pays d'origine ne poserait guère de problèmes.
6.1.2 Sur la base de l'ensemble de ces éléments, les juges cantonaux ont estimé que la situation personnelle du recourant ne s'opposait pas à la révocation de son autorisation d'établissement, car ses liens personnels et socioprofessionnels avec la Suisse n'avaient rien d'extraordinaire. La famille X.Y._ ne remplissait pas au surplus les conditions d'un cas individuel d'extrême gravité.
6.2 L'analyse faite par le Tribunal administratif n'est pas critiquable au regard des faits retenus dans l'arrêt entrepris, qui lient l'Autorité de céans (art. 105 al. 1 LTF). Au demeurant, on ajoutera que, contrairement à ce qu'il prétend, le recourant n'a pas respecté scrupuleusement l'ordre juridique suisse: non seulement il est entré illégalement en Suisse, mais encore il a dissimulé des faits essentiels aux autorités, comme on vient de le voir (cf. consid. 5, ci-dessus). De plus, le fait qu'il ait deux frères et une soeur qui vivent en Suisse n'est pas déterminant, puisqu'il est lui-même majeur et ne dépend pas d'eux. En conclusion, les juges cantonaux ont respecté le principe de la proportionnalité; ils n'ont donc pas abusé de leur pouvoir d'appréciation.
7. 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 solidairement les frais judiciaires (art. 65 ainsi que 66 al. 1 et 5 LTF). Il n'y a pas lieu d'allouer des dépens (art. 68 al. 1 et 3 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière de droit public est rejeté dans la mesure où il est recevable.
2. Le recours constitutionnel subsidiaire est irrecevable.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
4. Le présent arrêt est communiqué au mandataire des recourants, au Service des migrations, au Département de l'économie et à la Cour de droit public du Tribunal administratif du canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 31 mai 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Zünd Dupraz