Faits:
A. Dans le cadre d'une enquête pénale menée contre Y._, notamment pour infractions contre le patrimoine et en matière de fausse monnaie, divers faits troublants conduisirent les enquêteurs à soupçonner X._, sergent de gendarmerie et ami du prénommé, de fournir à ce denier diverses informations, en particulier sur l'état d'avancement de l'enquête pénale dirigée à son encontre. Ces soupçons se sont renforcés lorsque X._, surpris au milieu de la nuit dans le bureau des enquêteurs chargés de l'affaire Y._, a fourni des explications peu convaincantes sur les raisons d'une présence suspecte à cet endroit. Cet épisode a conduit à l'arrestation de X._ et à l'ouverture d'une instruction à son encontre.
B. Par jugement du 20 juin 2007, le Tribunal correctionnel du district de Neuchâtel a condamné X._, pour complicité de vol, complicité de dommages à la propriété, complicité de faux dans les certificats, tentative d'instigation d'induction de la justice en erreur, entrave à l'action pénale, tentative d'instigation de faux témoignage, abus d'autorité, violation du secret de fonction et corruption passive, à une peine privative de liberté de 30 mois, sous déduction de la détention préventive subie, 12 mois étant prononcés ferme, le solde de 18 mois étant assorti d'un sursis d'une durée de 5 ans.
Par arrêt du 5 mai 2009, la Cour de cassation pénale du Tribunal cantonal neuchâtelois a rejeté le pourvoi de X._.
C. Ce dernier dépose un recours en matière pénale au Tribunal fédéral. Invoquant l'arbitraire et une violation des art. 47 et 305 CP, il conclut, principalement, à ce qu'il soit condamné à une peine privative de liberté de 24 mois, sous déduction de la peine déjà exécutée, assortie du sursis pendant une durée de 5 ans. Il requiert l'effet suspensif et l'assistance judiciaire.

Considérant en droit:
1. 1.1 Aux termes de l'<ref-law>, le recours est recevable contre les décisions prises par les autorités cantonales de dernière instance. Partant, dans la mesure où le recourant s'en prend au jugement de première instance, sans critiquer les arguments que la Cour de cassation lui a opposés, ses griefs sont irrecevables.
1.2 Le recours ordinaire au Tribunal fédéral peut notamment être formé pour violation du droit fédéral (<ref-law>), y compris les droits constitutionnels. Sous peine d'irrecevabilité, il doit être motivé conformément à l'<ref-law>, respectivement l'<ref-law> pour les griefs mentionnés à cette disposition, dont les exigences correspondent à celles qui résultaient de l'art. 90 al. 1 let. b OJ (<ref-ruling> consid. 1.4 p. 287).
2. Invoquant l'arbitraire et une violation de l'<ref-law>, le recourant conteste sa condamnation pour entrave à l'action pénale. Il estime que les éléments du dossier ne permettent pas de retenir que les renseignements qu'il a fournis à Y._ auraient permis à ce dernier de se soustraire effectivement à l'action pénale.
2.1 Aux termes de l'<ref-law>, celui qui aura soustrait une personne à une poursuite pénale ou à l'exécution d'une peine ou d'une des mesures prévues aux art. 59 à 61, 63 et 64 sera puni d'une peine privative de liberté de trois ans au plus ou d'une peine pécuniaire.
La notion de soustraction présuppose que l'auteur a empêché une action de l'autorité dans le cours d'une procédure pénale au moins durant un certain temps. Elle est réalisée lorsque, par exemple, une mesure de contrainte relevant du droit de procédure telle qu'une arrestation est retardée par l'action du fauteur. Un simple acte d'assistance qui ne gêne ou perturbe la poursuite pénale que passagèrement ou de manière insignifiante ne suffit dès lors pas. Au nombre des actes qui entrent en ligne de compte s'agissant d'une entrave à l'action pénale, on trouve entre autres la dissimulation de moyens de preuve afin de retarder l'élucidation de l'affaire en faveur de la personne poursuivie, ainsi que l'hébergement temporaire d'un fugitif ou le transport d'une personne recherchée par les autorités de poursuite pénale et le soutien matériel procuré. Dans tous les cas, il faut démontrer que le fugitif, le suspect ou l'auteur a été soustrait durant un certain temps à l'action de la police du fait du prétendu fauteur (<ref-ruling> consid. 2.1 p. 140).
2.1.1 Selon les faits retenus, le recourant a consulté, entre octobre 2004 et février 2006, des informations confidentielles figurant dans les bases de données de la police au sujet d'enquêtes pénales en cours contre Y._ et ses complices présumés et les a transmises à celui-là. Il lui a également remis le contenu d'une note interne du 29 octobre 2004, envoyée à tous les postes de gendarmerie, note qui demandait aux policiers de surveiller Y._ et de signaler ses allées et venues, ses contacts et tout autre fait utile aux enquêteurs qui s'occupaient de la tentative de brigandage commise au préjudice de Z._. Il l'a aussi informé, vers fin 2004, du contenu d'un rapport de police qui mentionnait des écoutes téléphoniques sur son compte et celui d'un complice présumé. Au regard de la nature et de l'origine des données transmises, les autorités cantonales pouvaient, sans arbitraire, admettre que les renseignements précités avaient permis à Y._ d'adopter un comportement qui lui avait permis d'échapper momentanément à l'enquête pénale le concernant. Il avait ainsi pu se soustraire à l'action de la justice pendant une relativement longue période, soit du mois d'octobre 2004 jusqu'au début du mois de février 2006.
Sur la base de ces éléments, les autorités cantonales n'ont pas violé le droit fédéral en admettant que le recourant s'était rendu coupable d'entrave à l'action pénale, la condition de la soustraction telle que définie ci-dessus étant manifestement réalisée.
2.1.2 Selon les constatations cantonales, le recourant a consulté, à la demande de Y._, des informations confidentielles figurant dans les bases de données de la police au sujet des noms et adresses de détenteurs de véhicules que le prénommé avait l'intention de voler. Il lui a fourni lesdits renseignements, tout en sachant ou devant présumer que Y._ se livrait, avec des tiers, à des vols de voitures, dans le cadre d'un trafic entre la Suisse et les pays de l'Est. Il l'a également informé, vers la fin 2005 ou le début 2006, que la police avait reçu pour mission d'effectuer des surveillances des garages et de leurs alentours, suite à de nombreux vols de véhicules. Vu la nature et l'origine des informations transmises et le statut professionnel du recourant, les autorités cantonales pouvaient, sans arbitraire, admettre que ces données avaient incité Y._ à faire preuve de prudence et lui avaient ainsi permis d'échapper, certes pour une période plus limitée, à l'action de la justice pénale.
Au regard de ces éléments, les autorités cantonales n'ont pas violé le droit fédéral en admettant que le recourant s'était rendu coupable d'entrave à l'action pénale, la condition de la soustraction telle que définie ci-dessus étant manifestement réalisée.
3. Invoquant l'arbitraire et une violation des art. 47 et 50 CP, le recourant se plaint de la peine infligée.
3.1 La fixation de la peine est régie par l'<ref-law>, qui correspond à l'art. 63 aCP et à la jurisprudence y relative qui garde donc sa valeur. Selon l'<ref-law>, le juge doit motiver sa décision de manière suffisante. Sa motivation doit permettre de vérifier s'il a été tenu compte de tous les éléments pertinents et comment ils ont été appréciés (cf. <ref-ruling> consid. 4.2.1; <ref-ruling> consid. 3a).
Le Tribunal fédéral peut intervenir, en considérant le droit fédéral comme violé, si la sanction a été fixée en-dehors du cadre légal, si elle se base sur des critères juridiquement non déterminants, si elle ne prend pas en compte des points de vue essentiels ou si le juge s'est montré à ce point sévère ou clément que l'on doive parler d'un abus de son pouvoir d'appréciation (<ref-ruling> consid. 6.1 p. 21).
3.2 Le recourant estime que la peine est insuffisamment motivée.
Conformément à l'appréciation de la Cour de cassation (cf. arrêt du 5 mai 2007, p. 7 et 8), la motivation de la peine figurant aux pages 17 à 21 du jugement de première instance est clairement suffisante, comme le montre d'ailleurs le fait que le recourant est à même de la critiquer. Elle permet de discerner quels sont les éléments essentiels qui ont été pris en compte et s'ils l'ont été dans un sens aggravant ou atténuant. On comprend sans difficulté ce qui a guidé les premiers juges dans leur solution, qui ne viole donc pas l'<ref-law>.
3.3 Se référant à diverses affaires, le recourant se plaint d'une inégalité de traitement dans le cadre de la fixation de la peine.
Compte tenu des nombreux paramètres qui interviennent dans la fixation de la peine, une comparaison avec des affaires concernant d'autres accusés et des faits différents est d'emblée délicate. Il ne suffirait d'ailleurs pas que le recourant puisse citer un ou deux cas où une peine particulièrement clémente a été fixée pour prétendre à un droit à l'égalité de traitement (<ref-ruling> consid. 3a p. 144). Les arrêts invoqués par le recourant ne permettent aucune déduction significative du point de vue de la peine. Ils concernent d'autres accusés et des infractions différentes. La comparaison voulue par l'intéressé apparaît stérile et ne saurait donc être menée.
3.4 Invoquant l'interdiction de la double prise en considération, le recourant estime que sa qualité de gendarme constitue déjà un élément constitutif des principales infractions retenues à charge, de sorte que cet élément ne saurait être mis en avant dans le cadre de l'appréciation de sa culpabilité.
Au stade de la fixation de la peine, les autorités cantonales ont constaté que l'intégrité d'un des piliers essentiels au bon fonctionnement de la société, à savoir l'institution même de la police, avait été gravement bafouée par le comportement particulièrement répréhensible du recourant. Elles ont relevé que si certaines infractions retenues impliquaient la qualité de fonctionnaire dans leurs éléments constitutifs (art. 312, 320, 322 quater CP), elles ne pouvaient pour autant, au moment d'apprécier la quotité de la peine, faire abstraction du rôle particulier de l'intéressé dans la société en sa qualité de gendarme, jouissant en sus d'une longue expérience et de certains grades. Elles ont donc conclu que le comportement de l'accusé était particulièrement intolérable, non seulement à l'égard des lésés, mais également vis-à-vis de ses propres collègues, dont il avait réduit à néant certains de leurs efforts pour mettre un terme à la carrière criminelle de Y._, ainsi qu'à l'égard de l'institution de la police elle-même sur laquelle il avait jeté le discrédit.
Cette analyse ne viole en rien le droit fédéral, les autorités n'ayant nullement ignoré que certaines des infractions retenues impliquaient déjà certaines qualités propres à l'auteur et la peine devant être fixée en fonction de la gravité de la faute, qui doit également être évaluée au regard des circonstances et de la personne de l'auteur. Le grief est donc rejeté.
3.5 Le recourant motive ses actes par ses difficultés financières et conteste avoir agi par appât du gain et de l'argent facile.
S'agissant des mobiles de l'intéressé, les premiers juges ont retenu que même si celui-ci nourrissait certains liens affectifs à l'égard de Y._, sa motivation essentielle demeurait financière et que, même si le gain s'était finalement révélé modeste, cela ne l'empêchait pas d'en souhaiter une certaine régularité et d'en espérer davantage. Ils ont également estimé que la situation financière du recourant n'apparaissait pas modeste au point d'expliquer son comportement et qu'en outre, même s'il avait ressenti personnellement le besoin de trouver des ressources supplémentaires, rien ne l'empêchait dans ce cas de le faire par des moyens légaux (cf. jugement du 20 juin 2007 p. 17).
Par son argumentation, le recourant se livre à une critique purement appellatoire des faits retenus ci-dessus, en opposant sa version à celle de l'autorité cantonale, sans démontrer d'arbitraire d'une manière qui satisfasse un tant soit peu aux exigences de motivation de l'<ref-law> (cf. supra consid. 1.2). Ses griefs sont dès lors irrecevables.
3.6 Le recourant reproche aux juges cantonaux d'avoir ignoré les éléments à décharge. Il se prévaut notamment de ses qualités professionnelles, de son rôle très subsidiaire dans la commission des infractions, du fait que seule la tentative a été retenue pour certaines d'entre elles, de l'effet de la peine sur son avenir, de l'absence de risque de récidive, du fait qu'il était sous l'emprise de Y._, de son bon comportement durant la procédure et de son absence d'antécédents.
Pour l'essentiel, le grief est vain, les premiers juges ayant clairement exposé les éléments précités, tels que le parcours professionnel du recourant, lequel n'est d'ailleurs pas exempt de toute critique (cf. jugement du 20 juin 2007 p. 18 et 19), son rôle dans le cadre des infractions commises et le degré de réalisation de ces dernières (cf. jugement du 20 juin 2007 p. 9 à 16 et p. 22), l'effet de la peine sur son avenir (cf. jugement du 20 juin 2007 p. 20 à 21), son comportement durant la procédure (cf. jugement du 20 juin 2007 p. 20), les faits retenus ne réalisant par ailleurs aucunement la circonstance du repentir sincère au sens de l'art. 48 let d CP, et son absence d'antécédents (cf. jugement du 20 juin 2007 p. 18).
Pour le reste, en affirmant avoir été sous l'emprise de Y._, le recourant invoque un fait nouveau, sans l'étayer par des pièces précises du dossier, de sorte que sa critique est irrecevable (cf. <ref-law>).
3.7 En conclusion, aucun élément pertinent pour la fixation de la peine n'a été omis ou pris en considération à tort. Pour le reste, au vu des éléments à prendre en compte dans le cas d'espèce et exposés de manière exhaustive aux pages 17 à 21 du jugement de première instance, on ne saurait dire que, par sa quotité, la sanction serait à ce point sévère que la Cour cantonale doive se voir reprocher un abus de son pouvoir d'appréciation.
4. Invoquant une motivation insuffisante et un excès du pouvoir d'appréciation, le recourant se plaint du sursis partiel et plus particulièrement de la quotité de la peine ferme qui lui a été infligée.
4.1 Lorsqu'il prononce une peine privative assortie d'un sursis partiel, le juge doit non seulement fixer au moment du jugement la quotité de la peine qui est exécutoire et celle qui est assortie du sursis, mais également mettre en proportion adéquate une partie à l'autre. Pour fixer dans ce cadre la durée de la partie ferme et avec sursis de la peine, le juge dispose d'un large pouvoir d'appréciation. A titre de critère de cette appréciation, il y a lieu de tenir compte de façon appropriée de la faute de l'auteur (<ref-law>). Le rapport entre ces deux parties de la peine doit être fixé de telle manière que, d'une part, la probabilité d'un comportement futur de l'auteur conforme à la loi, mais aussi sa culpabilité soient équitablement prises en compte. Ainsi, plus le pronostic est favorable et moins l'acte apparaît blâmable, plus la partie de la peine assortie du sursis doit être importante. Mais en même temps, la partie ferme de la peine doit demeurer proportionnée aux divers aspects de la faute (<ref-ruling> consid. 5.6 p. 15).
4.2 Les autorités cantonales ont motivé leur décision relative au sursis et n'ont pas outrepassé leur large pouvoir d'appréciation, en s'écartant du minimum légal et en fixant à douze mois la partie de la peine à exécuter. En effet, d'une part, la faute du recourant est lourde (cf. jugement du 20 juin 2007 p. 17 ss). D'autre part, sa prise de conscience n'est que relative (cf. jugement du 20 juin 2007 p. 20). Enfin, la partie ferme de la peine pourra éventuellement être exécutée sous forme de semi-détention dans la mesure où les conditions posées par l'<ref-law> devaient être réalisées. Le grief est donc infondé.
5. Le recours doit ainsi être rejeté dans la mesure où il est recevable. Comme il était d'emblée voué à l'échec, l'assistance judiciaire ne peut être accordée (<ref-law>), de sorte que le recourant devra supporter les frais (<ref-law>), dont le montant sera toutefois arrêté en tenant compte de sa situation financière.
La cause étant tranchée, la requête d'effet suspensif devient sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La requête d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 1'600 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et à la Cour de cassation pénale du Tribunal cantonal du canton de Neuchâtel.
Lausanne, le 24 juillet 2009
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: La Greffière:
Favre Bendani