Faits:
A. X._ (ci-après: le recourant ou l'intéressé), ressortissant turc né en 1970, est entré illégalement en Suisse en 2001. Le 16 janvier 2003, il a épousé A._ née B._, ressortissante française au bénéfice d'une autorisation d'établissement et s'est vu octroyer une autorisation annuelle de séjour. Le 17 janvier 2006, il a annoncé au service des signalements de la police cantonale du canton de Neuchâtel la disparition de son épouse. Un rapport de police du 22 janvier 2006 confirmait le départ de celle-ci en compagnie de C._ en janvier 2006. Ils n'avaient pas laissé de nouvelle adresse. Le contrôle des habitants de Y._ a également établi que A._ avait noué des relations intimes avec C._, lequel avait déposé ses papiers à Y._ le 29 octobre 2005 et habitait à la même adresse que celle-ci.
B. Le 5 décembre 2007, le Service des étrangers du canton de Neuchâtel (actuellement et ci-après: le Service des migrations) a averti X._ qu'il ne comptait pas prolonger son autorisation de séjour, étant donné que celui-ci ne vivait plus de manière régulière avec son épouse depuis le début janvier 2006, date du départ de cette dernière. Par décision du 30 avril 2008, le Service des migrations n'a pas prolongé l'autorisation annuelle de séjour (permis B CE/AELE) de X._ et lui a imparti un délai échéant au 15 juin 2008 pour quitter le territoire cantonal. L'autorisation de séjour annuelle était entretemps, soit le 16 janvier 2008, arrivée à échéance.
Le 18 décembre 2008, le Conseiller d'Etat, Chef du Département de l'économie du canton de Neuchâtel (ci-après: le Conseiller d'Etat), a rejeté le recours interjeté par X._ contre la décision du Service des migrations.
C. Par arrêt du 26 juin 2009, le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté le recours de X._. Il a notamment retenu que le fond de l'affaire relevait encore de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE ou la loi sur le séjour et l'établissement des étrangers; RS 1 113; en vigueur jusqu'au 31 décembre 2007). L'intéressé se prévalait d'un mariage qui n'avait plus aucun contenu, ce qui constituait un abus de droit et rendait caduc tout droit à une autorisation. Le Tribunal administratif a également retenu que le recourant ne pouvait se prévaloir d'une situation d'extrême rigueur susceptible de conduire à l'octroi d'une autorisation de séjour après la dissolution du mariage ou de la communauté conjugale.
D. 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, d'annuler l'arrêt du Tribunal administratif du 26 juin 2009 et de prolonger son autorisation de séjour, subsidiairement, de renvoyer le dossier à "l'intimé" pour complément d'instruction ou pour qu'il soit statué dans le sens des considérants.
Le Service des migrations, le Conseiller d'Etat, ainsi que le Tribunal administratif, sans formuler d'observations, concluent au rejet du recours. L'Office fédéral des migrations a déposé des observations hors délai.
Par ordonnance du 3 septembre 2009, le Président de la IIe Cour de droit public du Tribunal de céans a admis la requête d'effet suspensif.

Considérant en droit:
1. Selon l'art. 126 al. 1 de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20), les demandes déposées avant l'entrée en vigueur de cette loi, le 1er janvier 2008, sont régies par l'ancien droit. Selon la jurisprudence constante du Tribunal fédéral, il n'y a pas lieu de se fonder sur la date de la décision de l'autorité inférieure pour déterminer le droit applicable mais sur celle de l'ouverture de la procédure (arrêt 2C_98/2009 du 10 juin 2009 consid. 1.4; arrêt 2C_329/2009 du 14 septembre 2009 consid. 2); ceci indépendamment du fait que la procédure ait été ouverte d'office ou sur demande de la personne concernée (arrêt 2C_745/2008 du 24 février 2009 consid. 1.2.3).
En l'espèce, le Service des migrations a averti le recourant qu'il ne comptait pas prolonger son autorisation de séjour étant donné qu'il ne vivait plus de manière régulière avec son épouse, par courrier du 5 décembre 2007. Cette date est déterminante pour juger de l'application du droit. Ainsi que l'a jugé à bon droit le Tribunal administratif, le fond de l'affaire est donc régi par la loi sur le séjour et l'établissement des étrangers, dans la mesure où la cause ne relève pas de 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 (ci-après: ALCP; RS 0.142.112.681).
2. 2.1 Selon l'art. 83 lettre 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.
D'après la jurisprudence (<ref-ruling> consid. 4, 8, 9 et 10), en vertu des art. 7 let. d ALCP et 3 par. 1 et 2 let. a annexe I ALCP, le conjoint étranger d'un travailleur communautaire disposant d'une autorisation de séjour ou d'établissement en Suisse peut se prévaloir d'un droit (dérivé) à une autorisation de séjour en Suisse pendant toute la durée formelle de son mariage, à l'image de ce que prévoit l'art. 7 al. 1 LSEE pour le conjoint étranger d'un ressortissant suisse (<ref-ruling> consid. 4.1 et 8.3 pp. 116 et 129).
En l'espèce, le recourant est toujours marié à une ressortissante française disposant d'une autorisation d'établissement. Son recours est, à cet égard, recevable, sans préjudice de l'existence d'un éventuel abus de droit qui concerne le fond de la cause (<ref-ruling> consid. 1.2 p. 343).
2.2 Au surplus, le recours est dirigé contre une décision finale (art. 90 LTF) rendue par un tribunal supérieur statuant en dernière instance cantonale (art. 86 al. 1 let. d et al. 2 LTF), et a été déposé en temps utile (art. 100 al. 1 et 46 al. 1 let. c LTF), ainsi que dans les formes prescrites (art. 42 LTF), par le destinataire du jugement attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (art. 89 al. 1 LTF). Par conséquent, il convient d'entrer en matière.
3. Le litige porte sur le droit du recourant à obtenir le renouvellement de son autorisation de séjour, plus précisément sur le point de savoir si l'invocation d'un tel droit revêt, ou non, un caractère abusif dans le cas d'espèce.
3.1 D'après la jurisprudence (<ref-ruling> consid. 4, 8, 9 et 10 p. 116/117 et 127 ss) relative à l'art. 3 par. 1 et 2 lettre a annexe I ALCP, le conjoint étranger d'un travailleur communautaire disposant d'une autorisation de séjour ou d'établissement en Suisse peut se prévaloir de droits d'une portée analogue à ceux dont bénéficie le conjoint étranger d'un citoyen suisse en vertu de l'art. 7 al. 1 LSEE.
Par conséquent, à l'instar des étrangers mariés à un citoyen suisse, les étrangers mariés à un travailleur communautaire jouissent, en principe, d'un droit de séjour en Suisse pendant toute la durée formelle du mariage, attendu qu'ils n'ont pas à vivre "en permanence" sous le même toit que leur époux pour être titulaire d'un tel droit. Ce droit n'est cependant pas absolu. Il y a notamment abus de droit à invoquer cette disposition lorsque le lien conjugal est vidé de toute substance et que la demande de regroupement familial vise seulement à obtenir une autorisation de séjour pour l'époux du travailleur communautaire. A cet égard, les critères élaborés par la jurisprudence rendue à propos de l'art. 7 al. 1 LSEE s'appliquent mutatis mutandis afin de garantir le respect du principe de non-discrimination inscrit à l'art. 2 ALCP et d'assurer une certaine cohésion d'ensemble au système (cf. arrêt 2C_238/2009 du 10 septembre 2009 consid. 4.1).
S'il n'est pas obligatoire que les époux vivent ensemble, il faut que demeure la possibilité d'une reprise de la vie commune. Des indices clairs et concrets que tel ne sera pas le cas permettent de conclure au caractère abusif de la requête (<ref-ruling> consid. 2.2 p. 151). L'absence de cohabitation pendant une période significative constitue, notamment, un indice permettant de dire que les époux ne veulent plus mener une véritable vie conjugale. Sauf circonstances particulières, on doit considérer le lien conjugal comme vidé de son contenu deux ans après la fin de la vie commune (<ref-ruling> consid. 10.3 et 10.4 p. 135 ss).
En l'espèce, les époux ne vivent plus ensemble depuis le mois de janvier 2006 au moins, ce que le recourant ne conteste pas. Dans la mesure où l'épouse, qui a quitté le domicile conjugal, n'a même pas informé le recourant de son nouveau lieu de résidence, toute perspective de reprise de vie commune semble illusoire; ce d'autant plus que l'épouse a quitté le recourant pour un tiers. Ainsi, contrairement à ce que prétend le recourant, point n'est besoin d'attendre une éventuelle déclaration d'absence (art. 35 ss CC) concernant son épouse. Partant, c'est à bon droit que le Tribunal administratif a estimé que, en se prévalant de son mariage, le recourant commettait un abus de droit. Le grief de mauvaise application du droit fédéral doit donc être rejeté.
4. Le recourant fait également valoir son intégration au monde du travail - en produisant notamment de nouvelles pièces qui, à titre de nova, sont irrecevables (art. 99 al. 1 LTF) - et sa volonté d'autonomie économique, ainsi que le fait qu'il assume les dettes laissées par son épouse et qu'il séjourne en Suisse depuis un certain nombre d'années tout en maîtrisant la langue et en se conformant aux lois suisses.
Dans la mesure où, ce faisant, et d'une manière ne répondant pas à l'obligation de motivation de l'art. 42 al. 2 LTF, le recourant entend faire valoir un cas de rigueur, force est de constater que les conditions prévalant à sa reconnaissance ne sont pas remplies en l'espèce. Il suffit, à cet égard, de renvoyer au consid. 6 de l'arrêt entrepris (art. 109 al. 3 LTF). En tant que le recourant tenterait, de la sorte, de se prévaloir de l'art. 4 LSEE, son recours se révèlerait irrecevable, dès lors que cette norme ne lui confère pas un droit à une autorisation, au sens de l'art. 83 let c ch. 2 LTF. Cette disposition autorise en effet les autorités compétentes à statuer librement, dans le cadre des prescriptions légales, sur l'octroi ou le refus d'autorisations de séjour ou d'établissement (<ref-ruling>). L'existence même de ce large pouvoir d'appréciation est à la base du régime d'exclusion du recours en matière de droit public.
5. Le recourant invoque l'art. 50 LEtr qui prévoit qu'après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste lorsque l'union conjugale a duré au moins trois ans et l'intégration est réussie (al. 1 let. a). L'intéressé met précisément en avant sa bonne intégration.
Si tous les éléments déterminants d'une cause se sont déroulés, comme c'est le cas en l'espèce, avant l'entrée en vigueur de la loi sur les étrangers, celle-ci reste alors soumise, respectivement est traitée en application de la loi précédemment en vigueur, soit la loi sur le séjour et l'établissement des étrangers (arrêt 2C_238/2009 du 10 septembre 2009 consid. 5). Partant, l'art. 50 LEtr n'est pas applicable à la présente cause et le grief est irrecevable.
6. Compte tenu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable.
Succombant, le recourant doit supporter les frais de l'instance (art. 66 al. 1 LTF) et il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté en tant que 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 mandataire de recourant, au Service des migrations, au Département de l'économie et au Tribunal administratif du canton de Neuchâtel, Cour de droit public, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 2 mars 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
R. Müller E. Kurtoglu-Jolidon