Faits:
A. X._, ressortissant angolais né en 1973, est arrivé en Suisse en 1990. Il y a déposé une demande d'asile qui a été rejetée. Il a renouvelé sa demande, en 1994, lors de son retour en Suisse. Le 16 août 1995, X._ a épousé, dans son pays d'origine, une citoyenne suisse. Il a alors rejoint notre pays et a obtenu une autorisation de séjour, puis une autorisation d'établissement le 6 septembre 2000.
Le divorce des époux X._ a été prononcé par jugement du 10 décembre 2002. Le 29 décembre 2005, l'intéressé s'est remarié avec une ressortissante angolaise, titulaire d'un permis N. Ils ont eu un fils, A._, né le *** 2006, auquel a été délivré une autorisation d'établissement.
Par jugement du 25 octobre 2006, le Tribunal correctionnel du district de Boudry a condamné X._ à cinq ans de réclusion et prononcé son expulsion du territoire suisse pour une durée de dix ans, sans sursis. Il a retenu que l'intéressé avait commis des actes d'ordre sexuel avec des enfants en abusant de sa nièce pendant plusieurs années. Il a également été reconnu coupable de vols au préjudice de son employeur et de consommation de stupéfiants.
Le 21 août 2007, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a prononcé l'expulsion de X._ du territoire suisse et a fixé son départ au jour de sa libération. Outre le jugement du 25 octobre 2006, cette décision énumère différentes condamnations prononcées à l'égard de l'intéressé, soit:
- condamnation du 5 octobre 1998 à 20 jours d'arrêts avec sursis, et à une amende de 500 fr., pour avoir circulé malgré "un retrait ou un refus du permis de conduire",
- condamnation du 9 mars 1999 à 1 mois et 15 jours d'emprisonnement avec sursis pour recel et contravention à la loi sur les stupéfiants,
- condamnation du 5 décembre 2000 à une amende de 1'000 fr. avec sursis pour violation grave des règles de la circulation routière,
- condamnation du 30 juillet 2002 à 5 jours d'emprisonnement avec sursis, ainsi qu'à une amende de 200 fr., pour vol d'importance mineure et dommages à la propriété,
- condamnation du 5 novembre 2002 à 7 jours d'emprisonnement pour violation des règles de la circulation routière et conduite en étant pris de boisson.
Le 15 septembre 2008, le Service des migrations a octroyé à l'épouse de X._ une autorisation de séjour en raison des problèmes de santé de A._.
Par décision du 9 mars 2009, 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._ contre la décision d'expulsion susmentionnée.
B. Le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté, par arrêt du 21 août 2009, le recours de l'intéressé à l'encontre de la décision du 9 mars 2009. Il a en substance retenu que les circonstances exceptionnelles, qui seules auraient permis de trancher en faveur de X._ au vu de la gravité des infractions commises, n'étaient pas réalisées. C'était donc à bon droit, et sans abuser de son pouvoir d'appréciation, que le Département de l'économie avait confirmé la décision d'expulsion.
C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, de dire que son recours est bien fondé et d'annuler l'arrêt du 21 août 2009 du Tribunal administratif. Il invoque une violation des art. 10 et 11 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (ci-après: LSEE ou loi sur le séjour et l'établissement des étrangers; RS 1 113), en vigueur jusqu'au 31 décembre 2007, de l'art. 8 CEDH, ainsi que des art. 5 et 13 Cst.
Le Service des migrations et le Département de l'économie concluent au rejet du recours. Le Tribunal administratif se réfère aux motifs de l'arrêt attaqué et demande le rejet du recours. Il en va de même de l'Office fédéral des migrations.
Par ordonnance du 15 octobre 2009, le Président de la IIe Cour de droit public du Tribunal fédéral a rejeté la demande d'effet suspensif.
Le 7 janvier et 29 avril 2010, le Service des migrations a spontanément produit divers pièces dont une décision du 6 janvier 2010 en matière de libération conditionnelle.

Considérant en droit:
1. En vertu de l'art. 126 al. 1 de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20), entrée en vigueur le 1er janvier 2008, les demandes déposées avant cette entrée en vigueur restent régies par la loi fédérale sur le séjour et l'établissement des étrangers. Cette règle vaut pour toutes les procédures engagées, sur requête de l'étranger ou d'office, en première instance avant l'entrée en vigueur du nouveau droit.
En l'espèce, le Service cantonal a examiné d'office les conditions de séjour du recourant avant le 1er janvier 2008, la décision d'expulsion datant du 21 août 2007. Par conséquent, l'ancien droit est applicable à la présente cause.
2. Le recours est recevable comme recours en matière de droit public, au regard des art. 42 et art. 82 ss LTF. 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.
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 Service des migrations a produit pour la première fois devant l'Autorité de céans différentes pièces, postérieures à 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>).
4. Selon l'art. 10 al. 1 LSEE, l'étranger peut être expulsé de Suisse notamment s'il a été condamné par une autorité judiciaire pour crime ou délit (lettre a) ou 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 (lettre b). 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 les 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], en vigueur jusqu'au 31 décembre 2007; <ref-ruling>10 consid. 2.1 p. 112; <ref-ruling> consid. 3.3.4 p. 182).
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). Il y a lieu également d'examiner si l'on peut exiger des membres de la famille qui ont un droit de présence en Suisse qu'ils suivent l'étranger dont l'expulsion est en cause. Pour trancher cette question, l'autorité compétente ne doit pas statuer en fonction des convenances personnelles des intéressés, mais prendre objectivement en considération leur situation personnelle et l'ensemble des circonstances. Si l'on ne peut pas exiger des membres de la famille pouvant rester en Suisse qu'ils partent à l'étranger, cet élément doit entrer dans la pesée des intérêts en présence mais n'exclut pas nécessairement, en lui-même, un refus de l'autorisation de séjour ou une expulsion (cf. <ref-ruling> consid. 4.2 p. 23 et les références).
La protection de la vie privée et familiale garantie par l'art. 13 al. 1 Cst. correspond à celle qui est consacrée par l'art. 8 par. 1 CEDH (<ref-ruling> consid. 3 p. 285 ss.; <ref-ruling> consid. 4.2 p. 218 s. et les arrêts cités).
4.1 En l'espèce, le recourant soutient n'avoir pas commis d'actes d'ordre sexuel à l'encontre de sa nièce. Il a cependant été reconnu coupable à cet égard et condamné à cinq ans de réclusion, par le Tribunal correctionnel du district de Boudry le 25 octobre 2006, pour de tels actes perpétrés pendant plusieurs années, ainsi que pour d'autres délits. Il s'agit dès lors de tenir compte de cette condamnation qui a été confirmée par le Tribunal fédéral (arrêt 6B_82/2007 du 6 juin 2007). Ainsi, le motif d'expulsion de l'art. 10 al. 1 let. a LSEE est manifestement réalisé.
Il convient donc d'examiner si, en confirmant l'expulsion du recourant, l'arrêt attaqué a correctement pris en considération les intérêts en présence et s'il a respecté le principe de proportionnalité.
4.2 Comme susmentionné, par jugement du 25 octobre 2006, le recourant a été condamné pour vols et infractions à la loi sur les stupéfiants et, principalement, pour infractions contre l'intégrité sexuelle, à savoir des actes d'ordre sexuel avec des enfants et des personnes dépendantes, contrainte sexuelle et viol, ainsi que pornographie. Ces actes, qui ont commencé en 1992 et se sont terminés en 2003, ont été commis au préjudice de la nièce du recourant, née en 1987. Le Tribunal correctionnel du district de Boudry a retenu que le recourant avait fait subir des actes extrêmement graves à sa nièce, les répétant à de nombreuses reprises et la contraignant à être victime de plusieurs autres hommes.
Ainsi, sur la base des faits établis par l'autorité intimée, qui lient le Tribunal fédéral (<ref-law>), il apparaît que le recourant présente un danger important pour l'ordre et la sécurité publics. Compte tenu de la gravité des faits commis, seules des circonstances exceptionnelles permettraient de faire pencher la balance des intérêts en faveur du recourant. Ceci d'autant plus que, selon la jurisprudence, il existe un intérêt public prépondérant à expulser des étrangers qui ont en particulier commis des actes de violence ou d'ordre sexuel d'une certaine gravité, même lorsque ces étrangers vivent en Suisse depuis plusieurs années (ATF <ref-ruling> consid. 2c p. 436).
4.3 Au moment où est intervenu l'arrêt entrepris, le recourant vivait en Suisse depuis quatorze ans sans interruption. Cette durée n'est pas négligeable mais elle doit être relativisée puisque l'intéressé est incarcéré depuis octobre 2006. De plus, lorsqu'il était en liberté, il n'a pas été capable de s'insérer pleinement en Suisse (art. 10 al. 1 let. b LSEE). Dès 1998, il a en effet été condamné à plusieurs reprises pour des infractions à la loi sur les stupéfiants, à la loi sur la circulation routière et pour dommages à la propriété. En outre, bien qu'il invoque avoir toujours travaillé et qu'il prétend maîtriser le français et l'allemand, son intégration socioprofessionnelle n'est pas exceptionnelle.
Le recourant est arrivé en Suisse à 21 ans. Il a donc passé, dans sa patrie, les périodes importantes que sont l'enfance, l'adolescence et les premières années de vie de jeune adulte. Il parle ainsi la langue de son pays et en partage la culture. Ces éléments ne peuvent que faciliter le retour de l'intéressé dans son pays. De toute façon, les difficultés auxquelles il pourrait être confronté ne sont pas déterminantes compte tenu de la gravité des infractions dont il s'est rendu coupable.
4.4 Selon le recourant, le renvoyer dans son pays reviendrait, de fait, à le séparer de sa femme et de son fils, détenteur d'une autorisation d'établissement. Celui-ci souffre en effet d'allergies et d'eczéma. Or, le coût des médicaments nécessaires à son état est prohibitif en Angola. L'épouse du recourant a d'ailleurs obtenu une permis de séjour en Suisse pour cette raison. Dès lors, il paraît en effet difficile d'exiger de ces personnes qu'elles suivent le recourant dans son pays. Cet élément, qui doit entrer dans la pesée des intérêts, ne permet cependant pas en lui-même d'exclure l'expulsion, surtout lorsque le comportement de l'étranger rend la poursuite de son séjour en Suisse indésirable (cf. <ref-ruling> consid. 2 p. 6 et les arrêts cités). Quoi qu'il en soit, l'éventuelle atteinte au respect de la vie familiale que constitue la mesure litigieuse est compatible avec l'art. 8 par. 2 CEDH.
4.5 Compte tenu de ce qui précède, le Tribunal administratif a correctement appliqué les critères pertinents afin d'évaluer si l'expulsion du recourant était ou non proportionnée. En confirmant celle-ci, il n'a en outre pas abusé de son pouvoir d'appréciation.
5. Selon le recourant, l'arrêt attaqué violerait l'art. 5 Cst. Celui-ci se contente toutefois de mentionner cette disposition sans développer son argumentation d'une façon qui réponde aux exigences découlant de l'<ref-law> (cf. <ref-ruling> consid. 1.5 p. 674, 232 consid. 1.2 p. 234). Partant, ce grief est irrecevable.
6. Les considérants qui précèdent conduisent au rejet du recours. Succombant, le recourant supporte les frais judiciaires (<ref-law>) et n'a pas droit à des dépens (<ref-law>).

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 à 1'500 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au 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 24 juin 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Zünd Kurtoglu-Jolidon