Faits:
A. A._, ressortissant algérien né en 1977, est arrivé en Suisse en juillet 1998, afin d'y étudier l'architecture. Le 7 janvier 2000, il a contracté mariage avec B._, citoyenne suisse née en 1966, divorcée et mère de deux enfants.
Le 4 avril 2003, A._ a déposé une demande de naturalisation facilitée fondée sur son mariage. Les époux ont contresigné, le 24 octobre 2003, une déclaration écrite aux termes de laquelle ils confirmaient vivre en communauté conjugale effective et stable, résider à la même adresse et n'envisager ni séparation, ni divorce. La déclaration signée précisait en outre que "si cet état de fait était dissimulé", la naturalisation facilitée pouvait être annulée dans les cinq ans. Par décision du 24 novembre 2003, l'Office fédéral de l'immigration, de l'intégration et de l'émigration (IMES, actuellement l'Office fédéral des migrations [ci-après: l'ODM]) a accordé la naturalisation facilitée à A._.
B. Le 16 novembre 2004, les époux ont introduit une requête commune de divorce auprès du Tribunal civil du district du Locle. Par jugement du 24 mars 2005, cette autorité a prononcé la dissolution du mariage. Le 8 juillet 2005, A._ a épousé une ressortissante tunisienne née en 1968. Deux enfants sont nés de cette union en août 2005 et en mars 2007. B._ a quant à elle épousé C._ le 13 décembre 2005.
Le 5 septembre 2005, l'ODM a informé A._ qu'il se voyait contraint d'examiner s'il y avait lieu d'annuler la naturalisation facilitée. Par divers courriers datés de septembre et d'octobre 2005, A._ expliqua par l'entremise de son conseil, qu'au cours de la période qui a suivi la signature de la déclaration commune la relation du couple s'était gravement dégradée. Il a également signalé un rapport de renseignements établi par la police neuchâteloise daté du 12 août 2003, lequel ferait état d'un foyer familial paraissant uni et serein.
Entendue par la gendarmerie du Locle le 7 janvier 2006, B._ a exposé que leur union s'était bien déroulée durant les deux premières années de mariage, mais que par la suite A._ avait changé de comportement: il participait peu aux frais du ménage, crachait sur elle, l'avait forcée à avoir des relations sexuelles, l'avait isolée socialement et rabaissé psychologiquement; il avait refusé qu'elle l'accompagne durant ses trois voyages en Algérie et lui avait demandé d'avorter à deux reprises, puis de se faire stériliser; enfin, il sortait seul le week-end pour la tromper. Elle ne se souvenait pas d'avoir signé une déclaration commune concernant la communauté conjugale et pensait que A._ la lui avait présentée comme un document quelconque. Elle a précisé que les difficultés conjugales étaient survenues après le 24 octobre 2003, sauf pour les humiliations et les viols et qu'elle avait été surprise lorsqu'il lui avait demandé de divorcer. Elle a encore ajouté qu'après l'octroi de sa naturalisation, A._ avait puisé sur son compte pour le paiement des factures et s'était bagarré avec ses deux enfants. Elle a enfin estimé qu'il avait profité d'elle pour acquérir la nationalité suisse.
Le 16 janvier 2006, B._ a déposé plainte pénale contre son ex-époux pour contrainte sexuelle, viol, voies de fait contre un enfant et violation du devoir d'assistance et d'éducation. Au cours de l'audition du 20 février 2006, A._ a contesté les accusations portées à son encontre. Il a précisé que les problèmes conjugaux avaient débuté à l'époque du retour du fils de son ex-épouse dans leur foyer.
Le 5 avril 2006, A._ s'est déterminé sur les déclarations de son ex-épouse et a précisé que celle-ci avait un équilibre psychologique précaire. Il ressort en effet de plusieurs rapports médicaux que B._ était traitée pour un trouble affectif bipolaire, qu'elle avait souffert de troubles du comportement liés à la consommation d'alcool et qu'elle était abstinente depuis 1998, avec quelques rechutes ponctuelles. Elle avait été hospitalisée à deux reprises dans un hôpital psychiatrique, de février à mai 2004, puis de juin à juillet 2005. Les 9 juin et 14 septembre 2006, A._ a notamment exposé que son ex-épouse avait subi un avortement à la double raison qu'elle prenait des médicaments susceptibles de causer des malformations au foetus et que le couple n'avait pas les moyens financiers pour entretenir un enfant. Il a confirmé disposer d'une procuration sur le compte de son ex-épouse et avoir effectué trois voyages dans son pays d'origine sans celle-ci, car la situation sécuritaire en Algérie était préoccupante.
Par jugement du 9 janvier 2007, le Tribunal correctionnel du district du Locle a acquitté A._ de l'ensemble des faits retenus contre lui. Il a considéré en substance que la description des viols était peu convaincante et que les témoignages recueillis durant l'instruction étaient, en majeure partie, à décharge de l'intéressé.
C. Par décision du 11 avril 2008, l'ODM a prononcé, avec l'assentiment de l'autorité cantonale compétente, l'annulation de la naturalisation facilitée accordée à A._ ainsi qu'à ses enfants. En substance, il a retenu que le mariage n'était pas constitutif d'une communauté conjugale effective et stable lors de la signature de la déclaration commune du 24 octobre 2003 et de l'octroi de la naturalisation facilitée, de sorte que celle-ci avait été obtenue sur la base de déclarations mensongères, voire de dissimulation de faits essentiels.
Le Tribunal administratif fédéral a confirmé la décision de l'ODM dans un arrêt rendu le 10 septembre 2009. Il a considéré en substance que l'enchaînement rapide des événements fondait la présomption que la communauté conjugale des intéressés n'était plus étroite et effective au moment de la signature de la déclaration commune, les éléments avancés par A._ n'étant pas suffisants pour renverser cette présomption.
D. Agissant par la voie du recours en matière de droit public, A._ demande principalement au Tribunal fédéral d'annuler cet arrêt et de constater qu'il dispose de la nationalité suisse. Il conclut subsidiairement au renvoi de la cause à l'instance précédente pour nouvelle décision au sens des considérants. Il se plaint d'une appréciation arbitraire des preuves, d'un établissement inexact des faits et d'une violation de l'art. 41 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (LN; RS 141.0).
L'ODM et le Tribunal administratif fédéral ont renoncé à se déterminer.

Considérant en droit:
1. Dirigé contre la décision du Tribunal administratif fédéral qui confirme l'annulation de la naturalisation facilitée accordée au recourant et à ses enfants, le recours est recevable comme recours en matière de droit public (art. 82 al. 1 let. a et 86 al. 1 let. a LTF). Le motif d'exclusion de l'<ref-law> n'entre pas en ligne de compte, dès lors qu'il s'agit en l'espèce de naturalisation facilitée et non pas de naturalisation ordinaire. Pour le surplus, le recourant a la qualité pour recourir au sens de l'<ref-law> et les conditions formelles de recevabilité sont remplies, de sorte qu'il y a lieu d'entrer en matière.
2. Le recourant conteste avoir obtenu la naturalisation par des déclarations mensongères. Il reproche au Tribunal administratif fédéral d'avoir apprécié de façon arbitraire les preuves et d'avoir établi les faits fondant le retrait de la naturalisation de façon manifestement inexacte, rendant ainsi une décision contraire à la LN. Il soutient également que l'instance précédente n'aurait pas tenu compte de circonstances pertinentes dans l'examen des éléments avancés pour renverser cette présomption.
2.1 Le recourant ne peut critiquer la constatation de faits, susceptibles d'avoir une influence déterminante sur l'issue de la procédure, que si ceux-ci ont été établis de manière manifestement inexacte ou en violation du droit au sens de l'<ref-law>, en particulier en violation de l'interdiction constitutionnelle de l'arbitraire (<ref-law>; <ref-ruling> consid. 4.3 p. 62; Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, FF 2001 p. 4135), ce qui signifie que le recourant doit formuler sa critique en respectant les exigences de motivation de l'<ref-law> (<ref-ruling> consid. 1.4.3 p. 254 s.).
Selon la jurisprudence, l'appréciation des preuves ou l'établissement des faits sont arbitraires (art. 9 Cst.; pour une définition de l'arbitraire cf. <ref-ruling> consid. 3.1 p. 265 s.; <ref-ruling> consid. 3.1 p. 153) lorsque l'autorité n'a manifestement pas compris le sens et la portée d'un moyen de preuve, si elle ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision ou lorsqu'elle tire des constatations insoutenables des éléments recueillis (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 2a p. 41).
2.2 Conformément aux art. 41 al. 1 LN et 14 al. 1 de l'ordonnance du 17 novembre 1999 sur l'organisation du Département fédéral de justice et police (RS 172.213.1), l'Office fédéral des migrations peut, avec l'assentiment de l'autorité du canton d'origine, annuler dans les cinq ans une naturalisation facilitée obtenue par des déclarations mensongères ou par la dissimulation de faits essentiels.
2.2.1 Pour qu'une naturalisation facilitée soit annulée, il ne suffit pas qu'elle ait été accordée alors que l'une ou l'autre de ses conditions n'était pas remplie; il faut qu'elle ait été acquise grâce à un comportement déloyal et trompeur. S'il n'est point besoin que ce comportement soit constitutif d'une escroquerie au sens du droit pénal, il est nécessaire que l'intéressé ait donné sciemment de fausses informations à l'autorité ou qu'il l'ait délibérément laissée dans l'erreur sur des faits qu'il savait essentiels (<ref-ruling> consid. 2 p. 165; <ref-ruling> consid. 3.1 p. 115 et les arrêts cités). Tel est notamment le cas si le requérant déclare vivre en communauté stable avec son conjoint alors qu'il envisage de se séparer une fois obtenue la naturalisation facilitée; peu importe que son mariage se soit ou non déroulé jusqu'ici de manière harmonieuse (arrêt 1C_406/2009 du 28 octobre 2009 consid. 3.1.1 et l'arrêt cité).
La nature potestative de l'art. 41 al. 1 LN confère une certaine liberté d'appréciation à l'autorité compétente, qui doit toutefois s'abstenir de tout abus dans l'exercice de celle-ci. Commet un abus de son pouvoir d'appréciation l'autorité qui se fonde sur des critères inappropriés, ne tient pas compte de circonstances pertinentes ou rend une décision arbitraire, contraire au but de la loi ou au principe de la proportionnalité (<ref-ruling> consid. 3.1 p. 115; <ref-ruling> consid. 4a p. 101 et les arrêts cités).
D'après la jurisprudence, la notion de communauté conjugale suppose non seulement l'existence formelle d'un mariage, mais encore une véritable communauté de vie des conjoints; tel est le cas s'il existe une volonté commune et intacte de ceux-ci de maintenir une union conjugale stable; une séparation survenue peu après l'octroi de la naturalisation constitue un indice de l'absence de cette volonté lors de l'obtention de la citoyenneté suisse (<ref-ruling> consid. 2 p. 165; <ref-ruling> consid. 2 p. 484; <ref-ruling> consid. 3a p. 98; <ref-ruling> consid. 2b p. 52).
2.2.2 La procédure administrative fédérale est régie par le principe de la libre appréciation des preuves (art. 40 de la loi fédérale de procédure civile fédérale du 4 décembre 1947 [PCF; RS 273], applicable par renvoi de l'art. 19 de la loi fédérale du 20 décembre 1968 sur la procédure administrative [PA; RS 172.021]). Ce principe vaut également devant le Tribunal administratif fédéral (<ref-law>). L'administration supporte le fardeau de la preuve lorsque la décision intervient, comme en l'espèce, au détriment de l'administré. Cela étant, la jurisprudence admet dans certaines circonstances que l'autorité puisse se fonder sur une présomption. C'est notamment le cas pour établir que le conjoint naturalisé a menti lorsqu'il a déclaré former une union stable, dans la mesure où il s'agit d'un fait psychique, lié à des éléments relevant de la sphère intime, souvent inconnus de l'administration et difficiles à prouver (<ref-ruling> consid. 3 p. 166; <ref-ruling> consid. 3.2 p. 485). Partant, si l'enchaînement rapide des événements fonde la présomption de fait que la naturalisation a été obtenue frauduleusement, il incombe alors à l'administré de renverser cette présomption, en raison, non seulement de son devoir de collaborer à l'établissement des faits (<ref-law> ; cf. <ref-ruling> consid. 3 p. 166; <ref-ruling> consid. 3.2 p. 115 s.), mais encore de son propre intérêt (ATF <ref-ruling> consid. 3.2 p. 485 s.).
S'agissant d'une présomption de fait, qui ressortit à l'appréciation des preuves et ne modifie pas le fardeau de la preuve (cf. ATF <ref-ruling> consid. 3.2 p. 486), l'administré n'a pas besoin, pour la renverser, de rapporter la preuve contraire du fait présumé, à savoir faire acquérir à l'autorité la certitude qu'il n'a pas menti; il suffit qu'il parvienne à faire admettre l'existence d'une possibilité raisonnable qu'il n'ait pas menti en déclarant former une communauté stable avec son conjoint. Il peut le faire en rendant vraisemblable, soit la survenance d'un événement extraordinaire susceptible d'expliquer une détérioration rapide du lien conjugal, soit l'absence de conscience de la gravité de ses problèmes de couple et, ainsi, l'existence d'une véritable volonté de maintenir une union stable avec son conjoint lorsqu'il a signé la déclaration (<ref-ruling> consid. 3 p. 165 s. et les arrêts cités).
2.3 En l'espèce, le Tribunal administratif fédéral a considéré que le laps de temps relativement court entre l'arrivée en Suisse du recourant (juillet 1998), son mariage avec une Suissesse déjà mère de deux enfants et suivie médicalement pour des troubles psychiques (janvier 2000), la déclaration commune (octobre 2003), l'octroi de la naturalisation (novembre 2003), le dépôt de la requête commune de divorce (novembre 2004), le remariage du recourant (juillet 2005) et celui de son ex-épouse (décembre 2005) fondait la présomption que la naturalisation facilitée avait été obtenue frauduleusement. Le recourant ne discute pas vraiment cette présomption de fait, laquelle peut du reste effectivement se fonder sur un enchaînement rapide des événements. Conformément à la jurisprudence précitée, il s'agit donc uniquement de déterminer si l'intéressé est parvenu à renverser cette présomption en rendant vraisemblable, soit la survenance d'un événement extraordinaire susceptible d'expliquer une dégradation aussi rapide du lien conjugal, soit l'absence de conscience de la gravité des problèmes de couple au moment de la signature de la déclaration commune.
2.4 Le recourant prétend d'abord que le Tribunal administratif fédéral n'aurait pas dû prendre en compte les déclarations de l'ex-épouse, relatives au prétendu changement de comportement du recourant suite à l'obtention du passeport suisse. Ces propos auraient été tenus lors d'un séjour dans un hôpital psychiatrique, alors que la prénommée était dans un état psychologique précaire. Ils auraient en outre été écartés par le Tribunal correctionnel du district du Locle. L'intéressé perd cependant de vue que d'une part, le Tribunal administratif fédéral a lui-même précisé qu'il fallait se reporter avec circonspection aux déclarations de l'ex-épouse du recourant. D'autre part, dans son jugement du 9 janvier 2007, le Tribunal correctionnel du district du Locle a retenu que "les difficultés conjugales [avaient] pris une ampleur décisive à la fin de l'année 2003 lorsque le [recourant] avait acquis la nationalité suisse". Il a également relevé qu'en 2004 le recourant avait donné des coups de pieds à la fille de son ex-épouse, comportement regrettable mais qui n'était toutefois pas poursuivi d'office. Le Tribunal administratif fédéral pouvait donc retenir sans arbitraire que le seuil de tolérance du recourant à l'égard de sa première femme et de ses enfants avait diminué suite à l'obtention de la nationalité helvétique.
Le recourant met ensuite en évidence le rapport de renseignements du 12 août 2003 établi par la police cantonale neuchâteloise qui ferait état d'un foyer familial serein et uni. Ledit rapport n'est cependant pas aussi explicite et ne porte pas de jugement sur la communauté conjugale des ex-époux. Il se contente de relever que les enfants de B._ vivaient au sein du foyer et que "l'intéressé semblait bien les avoir acceptés". Peu importe cependant, puisque cet élément, antérieur à la déclaration commune, n'est pas en mesure d'affaiblir la présomption.
Le recourant fait encore valoir que son employeur, tout comme de nombreux médecins et comme la majorité des témoins entendus dans le cadre de l'affaire pénale l'ont décrit comme une personne attentionnée et respectueuse à l'égard de son épouse et des enfants de celle-ci, leur offrant un soutien conjugal, éducatif et financier. Ces témoignages ne permettent toutefois pas d'établir qu'au moment de la signature de la déclaration commune, l'harmonie existait toujours au sein du couple au point d'envisager la continuation de la vie commune.
Enfin, pour le recourant, la rupture serait due au retour du fils de son ex-épouse en juin 2004, ce qui aurait engendré des tensions dans le couple. Si cet élément peut tendre à confirmer les tensions au sein du couple, il n'est pas de nature à précipiter subitement la fin de la vie d'un couple marié depuis quatre ans, sauf à considérer que leur union n'était pas stable. Le recourant, qui s'était investi dans l'éducation des enfants de son ex-épouse et les considérait comme ses propres enfants, ne saurait attribuer l'échec de son mariage à la seule gestion d'une crise avec un enfant. Ce d'autant moins que le fils de sa première femme s'est constitué un domicile indépendant déjà en septembre 2004. De même, le recourant se prévaut en vain du fait que le dépôt de la requête de divorce correspond avec le premier séjour de son ex-femme dans un hôpital psychiatrique suite au décès du premier mari de celle-ci. Cet élément n'est pas susceptible de rendre vraisemblable que l'intéressé n'avait pas conscience de la gravité des problèmes de couple au moment de la signature de la déclaration commune.
2.5 En définitive, le recourant n'apporte aucun élément propre à démontrer la survenance d'un événement extraordinaire postérieur à la signature de la déclaration commune et susceptible d'expliquer une dégradation aussi rapide du lien conjugal. L'intéressé ne rend pas non plus vraisemblable qu'en octobre 2003, au moment de la signature de la déclaration commune, il n'avait pas conscience du fait que la communauté conjugale n'était plus orientée vers l'avenir. Les éléments qu'il a avancés ne suffisent pas à renverser la présomption établie. Il en découle que les conditions d'application de l'art. 41 LN sont réunies et que le Tribunal administratif fédéral n'a pas abusé de son pouvoir d'appréciation en confirmant l'annulation de la naturalisation facilitée qui avait été octroyée au recourant.
3. Il s'ensuit que le recours doit être rejeté. Le recourant, qui succombe, doit supporter les frais de la présente procédure (<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 francs, sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du recourant, à l'Office fédéral des migrations et à la Cour III du Tribunal administratif fédéral.
Lausanne, le 21 décembre 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Féraud Tornay Schaller