Faits:
A. Ressortissant de l'ex-Yougoslavie (Kosovo) né en 1975, A.X._ est arrivé en Suisse le 7 juin 1995 et y a déposé une demande d'asile qui a été définitivement rejetée le 28 décembre 1995. Il a été refoulé dans son pays le 24 décembre 1997. Revenu en Suisse le 1er avril 1998, l'intéressé a été admis provisoirement à titre collectif par décision du 9 juin 1999. Il a épousé une Suissesse le 27 octobre 1999 et a, par conséquent, obtenu, au titre du regroupement familial, une autorisation de séjour qui a été régulièrement prolongée, la dernière fois jusqu'au 27 octobre 2004. En 2002, il a eu un fils d'une relation extra-conjugale. Le jugement prononçant le divorce des époux X._ est entré en force le 8 mars 2006.
A.X._ a été condamné pour infractions à la loi fédérale du 19 décembre 1958 sur la circulation routière (LCR; RS 741.01), le 12 janvier 2004, à 14 jours d'emprisonnement avec sursis pendant 3 ans et, le 19 octobre 2004, à 25 jours d'emprisonnement avec sursis pendant 5 ans, le sursis accordé précédemment étant révoqué. En outre, par jugement du 23 juin 2005, il a été condamné pour infraction à la loi fédérale du 3 octobre 1951 sur les stupéfiants et les substances psychotropes (loi sur les stupéfiants, LStup; RS 812.121) à 5 ans de réclusion, cette peine étant assortie d'une mesure d'expulsion ferme du territoire suisse pour une durée de 10 ans.
Le 28 novembre 2007, le Service des migrations du canton de Neuchâtel (ci-après: le Service cantonal) a prononcé l'expulsion de A.X._ du territoire suisse pour une durée indéterminée et fixé son départ au jour de sa libération. Il a estimé que l'intérêt public à éloigner l'auteur d'un important trafic de stupéfiants l'emportait, d'une part, sur l'intérêt de ce dernier à rester à proximité de son fils ainsi que de son amie et, d'autre part, sur le déracinement ainsi que sur les difficultés d'adaptation auxquels il pourrait être confronté en cas de renvoi.
B. Le 16 octobre 2008, le Département de l'économie du canton de Neuchâtel (ci-après: le Département cantonal) a rejeté le recours de A.X._ contre la décision du Service cantonal du 28 novembre 2007. Il s'est référé en particulier au passé pénal de l'intéressé et a relevé que celui-ci avait poursuivi son activité délictueuse après sa libération conditionnelle, le 7 mars 2008.
C. Par arrêt du 31 mars 2009, 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 2008. Le Tribunal administratif a considéré que l'intéressé représentait un danger important pour l'ordre et la sécurité publics qui justifiait une éventuelle atteinte au respect de sa vie familiale et privée.
D. Le 4 mai 2009, A.X._ a déposé au Tribunal fédéral un recours en matière de droit public contre l'arrêt du Tribunal administratif du 31 mars 2009. Il conclut, sous suite de frais et dépens, à l'annulation de l'arrêt attaqué et au renvoi du dossier pour complément d'instruction et nouvelle décision. Il se plaint, en substance, d'arbitraire et de violation du principe de la proportionnalité.
Sans procéder à un échange d'écritures, le Tribunal fédéral a invité les autorités neuchâteloises à produire leurs dossiers respectifs. Le Tribunal administratif a fourni le dossier de la cause comprenant son propre dossier ainsi que ceux du Département cantonal et du Service cantonal. Le 27 mai 2009, le Service cantonal a encore envoyé la communication de la reconnaissance par A.X._ de son fils B._, ayant eu lieu le 11 mai 2009.
Le 2 juin 2009, le recourant a encore spontanément déposé des pièces.

Considérant en droit:
1. La loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113) a été abrogée par 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; cf. ch. I de l'annexe à l'art. 125 LEtr). En dépit des termes restrictifs de l'art. 126 al. 1 LEtr, l'ancien droit est applicable à toutes les procédures introduites avant le 1er janvier 2008, qu'elles aient été engagées d'office ou à la demande de l'intéressé (arrêts 2C_745/2008 du 24 février 2009 consid. 1.2.3 et 2C_723/2008 du 24 novembre 2008 consid. 1). Le Service cantonal a examiné d'office les conditions de séjour du recourant avant le 1er janvier 2008 puisqu'il a rendu, le 28 novembre 2007, la décision d'expulsion qui est à la base du présent litige. Par conséquent, c'est l'ancien droit qui est applicable.
2. Le présent recours est dirigé contre une décision finale (<ref-law>) rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF) dans une cause de droit public (<ref-law>); en outre, il a été formé en temps utile (art. 100 al. 1 et 46 al. 1 let. a LTF) et dans les formes prescrites (<ref-law>) par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>). Il est par conséquent recevable. Il échappe en particulier à la clause d'irrecevabilité de l'art. 83 let. c ch. 4 LTF, dans la mesure où l'expulsion litigieuse ne se fonde pas sur l'art. 121 al. 2 Cst., mais sur l'art. 10 al. 1 LSEE (cf. arrêt 2C_146/2009 du 3 juillet 2009 consid. 2).
3. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il peut cependant rectifier ou compléter d'office les constatations de l'autorité précédente si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>; cf. aussi <ref-law>). Par ailleurs, l'<ref-law> dispose qu'aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-ruling> consid. 1.4 p. 5).
Le recourant produit pour la première fois devant l'Autorité de céans différentes pièces, postérieures pour la plupart à l'arrêt attaqué. Il s'agit de pièces nouvelles que le Tribunal fédéral ne peut pas prendre en considération (<ref-law>). Il en va de même du document (communication de la reconnaissance du fils du recourant) produit le 27 mai 2009 par le Service cantonal.
4. 4.1 D'après l'art. 10 al. 1 let. a LSEE, un étranger peut être expulsé de Suisse ou d'un canton s'il a été condamné par une autorité judiciaire pour crime ou délit. L'expulsion ne sera toutefois prononcée que si elle paraît appropriée à l'ensemble des circonstances et conforme au principe de la proportionnalité, selon la pesée d'intérêts exigée par l'art. 11 al. 3 LSEE respectivement par l'art. 8 par. 2 CEDH (<ref-ruling>10 consid. 2.1 p. 112; <ref-ruling> consid. 3.3.4 p. 182). Pour apprécier ce qui est équitable, l'autorité tiendra notamment compte de la gravité de la faute commise par l'étranger, de la durée de son séjour en Suisse et du préjudice qu'il aurait à subir avec sa famille du fait de l'expulsion (art. 16 al. 3 du règlement d'exécution du 1er mars 1949 de la loi fédérale sur le séjour et l'établissement des étrangers [RSEE; RO 1949 I 232]; <ref-ruling>10 consid. 2.1 p. 112; <ref-ruling> consid. 3.3.4 p. 182). Bien qu'il ne puisse pas revoir la décision du point de vue de l'opportunité, le Tribunal fédéral contrôle librement, sous l'angle de la violation du droit fédéral, si les autorités cantonales ont correctement mis en oeuvre les critères prévus par les dispositions du droit fédéral susmentionnées et en particulier si, à la lumière desdits critères, l'expulsion s'avère ou non proportionnée. Le Tribunal fédéral s'abstient cependant de substituer sa propre appréciation à celle des autorités cantonales (<ref-ruling> consid. 2a p. 523; <ref-ruling> consid. 2a p. 435).
Lorsque le motif de l'expulsion est la commission d'un délit ou d'un crime, la peine infligée par le juge pénal est le premier critère servant à évaluer la gravité de la faute et à peser les intérêts (<ref-ruling> consid. 4.2 p. 23). La durée de présence en Suisse d'un étranger constitue un autre critère important; plus la durée de ce séjour aura été longue, plus les conditions pour prononcer l'expulsion administrative doivent être appréciées restrictivement. De plus, on tiendra particulièrement compte, pour estimer la proportionnalité de la mesure, de l'intensité des liens de l'étranger avec la Suisse et des difficultés de réintégration dans son pays d'origine (cf. ATF <ref-ruling> consid. 4.4.2 p. 190; <ref-ruling> consid. 2b p. 523 s.; <ref-ruling> consid. 2c p. 436).
4.2 En l'occurrence, le motif d'expulsion figurant à l'art. 10 al. 1 let. a LSEE est manifestement réalisé, puisque le recourant a été condamné par des autorités judiciaires "pour crime ou délit" à plusieurs années de privation de liberté. Il s'est en particulier vu infliger une peine de 5 ans de réclusion pour infraction à la loi sur les stupéfiants. En effet, l'intéressé a organisé un trafic de stupéfiants, dans lequel il assumait le rôle principal et qui portait sur des quantités très importantes de cocaïne pure (526,49 g). Or, il s'agit d'un domaine où la jurisprudence se montre particulièrement rigoureuse (cf. ATF <ref-ruling> consid. 2c p. 436). La protection de la collectivité publique face au développement du marché de la drogue constitue incontestablement un intérêt public prépondérant justifiant l'éloignement d'un étranger qui s'est rendu coupable d'infraction grave à la loi sur les stupéfiants. Les étrangers qui sont mêlés au commerce des stupéfiants doivent donc s'attendre à faire l'objet de mesures d'éloignement (arrêt 2C_530/2007 du 21 novembre 2007 consid. 5). En outre, d'après l'arrêt attaqué, le recourant, libéré conditionnellement le 7 mars 2008, a été interpellé en France au mois de juillet 2008 en possession de 7130 g d'herbe de cannabis, raison pour laquelle il a été condamné à 15 mois de prison ferme. Il ressort de ces faits que l'intéressé reste en contact avec les milieux qui se livrent au trafic de stupéfiants. Par conséquent, le risque de récidive apparaît élevé. Peu importe au demeurant que la condamnation prononcée en France ne soit pas définitive et exécutoire, dès lors qu'il s'agit d'apprécier le risque de récidive du recourant qui ne prétend du reste pas, dans le présent recours, qu'il n'aurait pas commis les faits qui lui ont valu cette condamnation. Quoi qu'il en soit, lorsque l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ALCP; RS 0.142.112.681) n'est pas applicable, le risque de récidive n'est pas déterminant, mais ne constitue qu'un facteur parmi d'autres dans la pesée des intérêts où la gravité des faits commis est le premier élément à prendre en considération (<ref-ruling> consid. 4.3 p. 24).
Par ailleurs, au moment où est intervenu l'arrêt entrepris, le recourant vivait en Suisse depuis 11 ans sans interruption, après y avoir séjourné pendant environ deux ans et demi. Cette durée n'est pas négligeable, mais elle doit être relativisée du fait que l'intéressé a passé plus de 3 ans en prison. Le recourant est arrivé en Suisse dans sa vingtième année; c'est donc dans sa patrie qu'il a vécu son enfance et son adolescence, périodes durant lesquelles se forge la personnalité; dès lors, il a incontestablement des racines socioculturelles dans son pays d'origine. De plus, il ressort de l'arrêt attaqué que son intégration socioprofessionnelle n'est pas exceptionnelle. Le recourant invoque enfin la relation qu'il entretient avec son fils. Le 31 mars 2009, lorsque le Tribunal administratif a statué, cet enfant, né en 2002, n'était pas reconnu par son père. Cela suffit à démentir la prétendue étroitesse de leur relation, quand bien même une reconnaissance a pu avoir lieu ultérieurement. Le recourant a attendu plusieurs années avant d'entreprendre des démarches pour reconnaître son enfant et ce n'est pas l'éventuelle lenteur de quelques formalités administratives qui pourrait expliquer que cette reconnaissance n'était pas encore effectuée plus de 6 ans après la naissance de l'enfant. En outre, le recourant a été incarcéré le 28 octobre 2004 pour plus de 3 ans, puisqu'il a été libéré conditionnellement le 7 mars 2008; à ses dires, c'est à partir de son premier congé, soit du 1er août 2006, qu'il a vu son enfant, qui avait déjà 4 ans. Ces seuls contacts, dont il n'est d'ailleurs pas démontré qu'ils aient été intenses, n'ont pas pour effet de rendre l'intérêt privé du recourant à rester en Suisse prépondérant par rapport à l'intérêt public à éloigner de ce pays un étranger qui a commis des infractions particulièrement graves.
On ne discerne donc aucune violation des art. 10 al. 1 LSEE, 11 al. 3 LSEE ou 16 al. 3 RSEE.
4.3 Le recourant reproche au Tribunal administratif d'avoir écarté arbitrairement l'application de l'art. 8 CEDH.
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.3.1 p. 211) avec une personne de sa famille ayant le droit de résider durablement en Suisse (cf. <ref-ruling> consid. 3.1 p. 285). D'après la jurisprudence, les relations familiales qui peuvent fonder, en vertu de l'art. 8 par. 1 CEDH, un droit à une autorisation de police des étrangers sont avant tout les rapports entre époux ainsi qu'entre parents et enfants mineurs vivant ensemble (<ref-ruling> consid. 1d p. 261).
Devant le Tribunal administratif, le recourant n'a pas établi le lien de filiation l'unissant à B._, ni d'ailleurs le statut (droit de résidence durable) de ce dernier. Par conséquent, en considérant que l'art. 8 par. 1 CEDH n'était pas applicable à son cas, les juges cantonaux ne sont pas tombés dans l'arbitraire. Au demeurant, le Tribunal administratif a précisé que, même si les conditions d'application de l'art. 8 par. 1 CEDH étaient réalisées, la mesure d'expulsion contestée serait compatible avec l'art. 8 par. 2 CEDH. En écartant ainsi au surplus l'argument que l'intéressé tirait de l'art. 8 CEDH, le Tribunal administratif a appliqué correctement le droit. En effet, la pesée des intérêts en présence effectuée sur la base de cette disposition est la même que celle qui se fonde sur les art. 10 al. 1 et 11 al. 3 LSEE ainsi que 16 al. 3 RSEE (<ref-ruling>10 consid. 2.1 p. 112). Les juges cantonaux n'avaient donc pas à reprendre, par rapport à l'art. 8 CEDH, la pesée des intérêts faite sous l'angle de la LSEE. Or, on a vu ci-dessus (consid. 4.2) que l'intérêt public était prépondérant en l'espèce.
5. Au vu de ce qui précède, le recours doit être rejeté.
Succombant, le recourant doit supporter les frais judiciaires (art. 65 et 66 al. 1 LTF) et n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué à la mandataire du recourant, 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 20 août 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Dupraz