Faits: A. Ressortissant d'ex-Yougoslavie (Kosovo) né en 1971, A.X._ est arrivé en Suisse en décembre 1991 et y a déposé une demande d'asile. Il a épousé une Suissesse, B._, le 27 février 1997, et s'est par conséquent vu octroyer, à partir de cette date, une autorisation de séjour à l'année. En mai 2002, il a été mis au bénéfice d'une autorisation d'établissement avec effet rétroactif au 27 février 2002. Les époux X._ ont cessé la vie commune à la mi-août 2002 et déposé, deux mois plus tard, une requête commune de divorce. Celui-ci a été prononcé le 3 juillet 2003. En décembre 2003, A.X._ a épousé, au Kosovo, une compatriote, Y._. En février 2004, cette dernière a demandé, au titre du regroupement familial, une autorisation d'entrée et de séjour pour elle et pour les deux enfants qu'elle avait eus avec A.X._ et qui étaient nés le 12 avril 2001 respectivement le 13 mai 2003. Interrogé sur la relation qu'il avait avec sa femme et ses enfants (date de la rencontre, nature durable de la relation, contacts et fréquence de ceux-ci), A.X._ a répondu le 15 juin 2004 au Service des étrangers, actuellement le Service des migrations, du canton de Neuchâtel (ci-après: le Service cantonal): "J'ai rencontré mon épouse, Y._, en août 2000 pendant les vacances. Je suis retourné en Suisse à la fin des vacances. Je la contactais toutes les deux semaines pour prendre de ses nouvelles. Je suis retourné au pays pour les fêtes de fin d'année et quand on s'est retrouvé, j'ai réalisé que c'était la femme de ma vie. Depuis ce moment-là, je n'ai cessé d'avoir des contacts avec elle par téléphone." Il a aussi précisé qu'à partir de Noël 2000, il était retourné régulièrement au Kosovo pour les fêtes de fin d'année, à Pâques, aux vacances horlogères et une semaine en automne. B. Le 10 février 2005, le Service cantonal a révoqué l'autorisation d'établissement de A.X._, en lui impartissant un délai échéant le 29 avril 2005 pour quitter le territoire neuchâtelois; il a en outre refusé les autorisations sollicitées par sa femme (autorisations d'entrée et de séjour pour elle et autorisations d'entrée et d'établissement pour ses enfants). Il a considéré que A.X._ avait obtenu le renouvellement de son autorisation de séjour et la délivrance de son autorisation d'établissement alors que son mariage n'existait plus que formellement. Il avait commis un abus de droit, en taisant qu'il n'allait pas poursuivre la vie commune, compte tenu de la relation qu'il entretenait avec une compatriote, qui lui avait donné deux enfants pendant son mariage avec une Suissesse. En cachant sa situation familiale réelle, il avait dissimulé des faits essentiels aux autorités. Contestant ses déclarations du 15 juin 2004, A.X._ a recouru contre la décision précitée du 10 février 2005. Le Département de l'économie du canton de Neuchâtel (ci-après: le Département cantonal) l'a débouté par décision du 16 octobre 2006. Il a repris, en la développant, l'argumentation du Service cantonal. C. Par arrêt du 10 octobre 2008, la Cour de droit public du Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté le recours de A.X._ contre la décision du Département cantonal du 16 octobre 2006. Les juges cantonaux ont considéré en substance qu'à la suite des déclarations du 15 juin 2004, le Département cantonal pouvait retenir, comme le Service cantonal, que l'intéressé avait obtenu une autorisation d'établissement sur la base d'indications fausses. La position du recourant, qui avait réfuté ultérieurement les explications fournies le 15 juin 2004, affirmant qu'il ignorait tout de sa première paternité pendant son mariage avec B.X._ et qu'il n'aurait reconnu son enfant et décidé d'entamer une relation conjugale avec Y._ qu'une fois son mariage dissous et après l'obtention de son autorisation d'établissement, n'a pas été jugée crédible. D. Le 13 novembre 2008, A.X._ a formé un recours en matière de droit public contre l'arrêt du Tribunal administratif du 10 octobre 2008. Il demande au Tribunal fédéral, sous suite de frais et dépens, principalement, d'annuler l'arrêt attaqué en tant qu'il confirme la révocation de son autorisation d'établissement et de constater qu'il a droit au maintien de cette autorisation. A titre subsidiaire, il conclut à la constatation que le Tribunal administratif a commis une violation du droit d'être entendu et au renvoi de la cause à la juridiction cantonale pour que cette violation soit réparée et qu'une nouvelle décision soit rendue. Le Tribunal administratif conclut au rejet du recours. Le Département cantonal demande au Tribunal fédéral de rejeter le recours, sous suite de frais. Le Service cantonal conclut, sous suite de frais, au rejet du recours dans la mesure de sa recevabilité. L'Office fédéral des migrations propose le rejet du recours. 