Faits:
A. A._, ressortissant algérien né en 1968, est arrivé en Suisse le 19 décembre 1994 et y a déposé une demande d'asile. Le 4 avril 1995, l'Office fédéral des réfugiés (actuellement Office fédéral des migrations [ODM]) a rejeté cette requête et a ordonné le renvoi de l'intéressé, qui a contesté cette décision auprès de la Commission suisse de recours en matière d'asile. Le 16 août 1996, A._ a épousé B._, ressortissante suisse née en 1962. En raison de ce mariage, il a retiré le recours qu'il avait formé auprès de la Commission suisse de recours en matière d'asile. Le 18 septembre 1996, il a obtenu une autorisation de séjour annuelle dans le canton de Fribourg pour vivre auprès de son épouse, autorisation qui a ensuite été régulièrement renouvelée jusqu'en 2001, année à partir de laquelle il a été mis au bénéfice d'une autorisation d'établissement.
Le 2 juillet 2001, A._ a déposé une demande de naturalisation facilitée fondée sur son mariage avec B._. Dans le cadre de l'instruction de cette demande, les époux ont contresigné, le 30 avril 2002, 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 est dissimulé", la naturalisation facilitée pouvait être annulée dans les cinq ans. Par décision du 10 juin 2002, l'Office fédéral des étrangers (OFE, actuellement l'ODM) a accordé la naturalisation facilitée à A._.
B. Le 28 septembre 2002, les époux A._ et B._ ont introduit auprès du Président du Tribunal civil de la Gruyère une requête commune de séparation de corps, en invoquant notamment "la mésentente quotidienne". Le mariage a été dissous par jugement du 1er septembre 2003. Le 28 décembre 2003, A._ a épousé une ressortissante algérienne, née en 1978. Le Service de l'état civil et des naturalisations du canton de Fribourg a dénoncé ce cas à l'Office fédéral de l'immigration, de l'intégration et de l'émigration (IMES, devenu ensuite l'ODM) en vue d'une éventuelle annulation de la naturalisation facilitée. L'intéressé a été invité à présenter des observations. Son ex-épouse a été entendue le 24 mars 2005.
Par décision du 14 juin 2005, l'ODM a prononcé l'annulation de la naturalisation facilitée, avec l'assentiment des autorités compétentes du canton de Fribourg. Cet office a considéré que le mariage de l'intéressé n'était pas constitutif d'une communauté conjugale effective et stable au moment de l'octroi de la naturalisation facilitée, de sorte que celle-ci avait été obtenue sur la base de déclarations mensongères et d'une dissimulation de faits essentiels.
C. A._ a recouru contre cette décision auprès du Département fédéral de justice et police. Il a souligné que la volonté de séparation provenait de son épouse et qu'elle était apparue dès la fin de l'été 2002, soit après la signature de la déclaration de vie commune le 30 avril 2002. La séparation avait été causée par ses déplacements professionnels à l'étranger, qui n'avaient débuté qu'en juillet 2002, soit bien après la signature de la déclaration du 30 avril 2002. Il indiquait que son ex-épouse avait ainsi "subitement" décidé de se séparer de lui à la fin de l'été 2002, "probablement en raison de son état de santé psychique". Il a également reproché à l'ODM de ne pas avoir pris en compte le fait que le couple avait attendu plus de sept mois pour confirmer sa volonté de divorcer et qu'une reprise de la vie commune avait été envisagée pendant cette période. Le 9 août 2007, A._ a en outre produit un certificat médical attestant du fait que le couple avait consulté un médecin de juillet 1997 à février 1998 pour des problèmes de stérilité. La cause a été transmise au Tribunal administratif fédéral, conformément à l'art. 53 al. 2 de la loi sur le Tribunal administratif fédéral (LTAF; RS 173.32).
Par arrêt du 17 mars 2008, le Tribunal administratif fédéral a rejeté ce recours. Il a considéré en substance que l'enchaînement rapide des événements - rejet de la demande d'asile, mariage avec une ressortissante suisse, naturalisation, séparation, divorce et remariage avec une compatriote plus jeune - fondait la présomption que le premier mariage de A._ avait pour but prépondérant de s'installer en Suisse et d'obtenir la naturalisation. L'intéressé n'avait pas pu rendre vraisemblable ni la survenance d'un événement extraordinaire permettant d'expliquer la dégradation rapide du lien conjugal, ni le fait qu'il n'avait pas conscience de la gravité des problèmes rencontrés par son couple au moment où il a signé la déclaration du 30 avril 2002. Ainsi, le Tribunal administratif fédéral a décidé de s'en tenir à la présomption susmentionnée, faute de "contre-preuves convaincante".
D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral de réformer la décision attaquée en ce sens que la naturalisation facilitée qui lui a été octroyée ne soit pas annulée. Subsidiairement, il requiert que la décision soit annulée et l'affaire renvoyée aux autorités précédentes pour qu'elles disent que la naturalisation facilitée n'est pas annulée. Il invoque l'interdiction de l'arbitraire (art. 9 Cst.) et se plaint 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). Il sollicite en outre l'octroi de l'effet suspensif. L'ODM et le Tribunal administratif fédéral ont renoncé à se déterminer.
E. Par ordonnance du 19 mai 2008, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif formulée par A._.
F. Le 8 juillet 2009, la Cour de céans a délibéré sur le présent recours en séance publique.

Considérant en droit:
1. L'arrêt entrepris émane du Tribunal administratif fédéral et concerne l'annulation de la naturalisation facilitée accordée au recourant, si bien qu'il peut faire l'objet d'un recours en matière de droit public devant la Cour de céans (art. 82 al. 1 let. a et 86 al. 1 let. a LTF, art. 29 al. 1 let. f RTF). 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 (cf. arrêt non publié 5A.7/2003 du 25 août 2003 et les références). 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. Affirmant que l'état de fait de l'arrêt attaqué est "vicié" au sens de l'<ref-law>, le recourant entreprend de le compléter en alléguant des faits qui n'ont pas été retenus par cet arrêt.
2.1 Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. 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). 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 En l'occurrence, le recourant relève à juste titre que deux faits pertinents n'ont pas été retenus par le Tribunal administratif fédéral alors qu'ils étaient clairement établis. Il s'agit d'abord du fait que le recourant et son épouse ont consulté un gynécologue à cinq reprises entre 1997 et 1998, pour cause de stérilité. Ces consultations ont été attestées dans un certificat établi le 17 juin 2005, et versé en cause le 9 août 2007, dans lequel le médecin en question précise ce qui suit: "souvenir et dossier concourent à affirmer un couple vrai". La démarche du recourant et de son épouse ainsi que les constations du médecin consulté sont des éléments importants dans l'appréciation du sérieux de l'union conjugale des intéressés et ils auraient dû être pris en considération, ce d'autant plus que le Tribunal administratif fédéral sous-entend à plusieurs reprises que le mariage en cause n'était pas sincère. Le second élément pertinent qui n'a pas été retenu par l'arrêt attaqué est le fait que le premier déplacement professionnel du recourant à l'étranger a eu lieu du 15 juillet au 20 septembre 2002, soit entre la signature de la déclaration commune et la séparation du couple. Ce voyage est établi par une attestation de l'employeur du recourant datée du 2 décembre 2004 et versée en cause le 11 février 2005. L'arrêt attaqué doit donc être complété sur ce point également. Pour le surplus, il n'y a pas lieu de s'écarter des faits retenus par l'autorité précédente.
3. 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.
3.1 Pour qu'une naturalisation facilitée soit annulée, il ne suffit pas qu'elle ait été obtenue 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 pas 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 l'ait délibérément laissée dans l'erreur sur des faits qu'il savait essentiels (<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 5A.22/2006 du 13 juillet 2006 consid. 2.2).
La nature potestative de l'art. 41 al. 1 LN confère une certaine latitude à l'autorité. Dans l'exercice de cette liberté, celle-ci doit s'abstenir de tout abus; 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; <ref-ruling> consid. 2 p. 310 et les arrêts cités).
3.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.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é, en raison non seulement de son devoir de collaborer à l'établissement des faits (<ref-law>; cf. <ref-ruling> consid. 3.2 p. 115 s.), mais encore dans son propre intérêt, de renverser cette présomption (<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. <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 au moment de la signature de la déclaration commune (<ref-ruling> consid. 3 p. 165 s.; arrêt 5A.12/2006 du 23 août 2006 consid. 2.3 et les arrêts cités).
4. En l'espèce, le Tribunal administratif fédéral a considéré que l'enchaînement rapide des événements - déclaration commune le 30 avril 2002, naturalisation le 10 juin 2002 et introduction d'une demande de séparation le 28 septembre 2002 - fondait la présomption que le couple n'envisageait déjà plus une vie future partagée lors de la signature de la déclaration de vie commune.
Il a estimé que cette présomption était renforcée par le fait que le mariage avait été conclu alors que le recourant risquait d'être renvoyé de Suisse. Il a ajouté qu' "à la lumière des us et coutumes prévalant en Algérie [...] la première épouse de l'intéressé ne présentait pas le profil typique généralement attendu en pareilles circonstances", de sorte qu'il était peu vraisemblable que le recourant ait pu avoir la conviction que sa communauté matrimoniale était stable, effective et tournée vers l'avenir. Cette argumentation est pour le moins discutable et ne repose sur aucun élément concret. Elle est en outre en contradiction avec divers éléments du dossier, qui démontrent que le recourant et sa première épouse formaient une réelle communauté conjugale. C'est en particulier le cas des déclarations de l'ex-épouse du recourant et du témoignage écrit des enfants de celle-ci, ainsi que de l'attestation selon laquelle le couple avait consulté un gynécologue entre 1997 et 1998 pour cause de stérilité, le médecin en question se souvenant en outre d'un "couple vrai". C'est donc en vain que l'autorité intimée s'est fondée sur les considérations précitées pour "renforcer" la présomption.
Quoi qu'il en soit, la présomption de fait n'est pas discutée en l'occurrence. Elle peut effectivement se fonder sur un enchaînement rapide des événements, la séparation du couple étant survenue seulement quatre à cinq mois après la signature de la déclaration commune du 30 avril 2002. Il s'agit dès lors uniquement de déterminer si le recourant a rendu vraisemblable qu'il n'avait pas menti en déclarant former une communauté stable avec son épouse et si la présomption sur laquelle se fonde l'annulation de la naturalisation facilitée a pu être renversée par l'intéressé.
5. Le Tribunal administratif fédéral a jugé en substance que la dégradation du couple avait été un long processus lié aux problèmes d'ordre psychologique rencontrés par l'ex-épouse du recourant et que les déplacements professionnels de celui-ci à l'étranger auraient "tout au plus appuyé l'état de déliquescence de cette union conjugale". L'intention de se séparer existait déjà au moment de la signature de la déclaration commune, en tout cas en ce qui concerne l'ex-épouse du recourant. Dès lors, le fait que cette dernière ait néanmoins signé la déclaration permettrait "de nourrir des doutes légitimes quant à la bonne foi des intéressés".
5.1 Il convient d'abord de souligner que le fait que l'ex-épouse du recourant ait signé la déclaration commune en doutant de la solidité de l'union conjugale n'est pas déterminant. En effet, il est exclu de fonder l'annulation de la naturalisation sur un élément qui relève d'un tiers. On ne saurait dès lors imputer au recourant d'éventuels mensonges ou omissions de son ex-épouse. Pour déterminer si le recourant a obtenu la naturalisation sur la base de déclarations mensongères, seule est pertinente la conscience qu'il pouvait avoir de la gravité des problèmes de son couple au moment où il a signé la déclaration du 30 avril 2002 et lorsqu'il a obtenu la naturalisation. A cet égard, contrairement à ce que retient l'arrêt attaqué, l'intéressé ne doit pas apporter de "contre-preuve", mais il doit simplement faire admettre, conformément à la jurisprudence rappelée précédemment, l'existence d'une possibilité raisonnable qu'il n'ait pas menti. Il convient en effet d'éviter un véritable renversement du fardeau de la preuve.
5.2 Pour renverser la présomption, le recourant soutient en substance que c'est son ex-épouse qui a décidé seule de mettre un terme à leur union en été 2002, soit après la signature de la déclaration de vie commune et l'obtention de la naturalisation facilitée. Cette volonté de de son ex-épouse était pour lui inattendue, mais il se serait finalement résigné à déposer une requête commune de séparation. Le recourant insiste également sur le fait que ce sont ses voyages professionnels à l'étranger qui ont amené son ex-épouse à demander la séparation.
Il est vrai que, lors de son audition du 24 mars 2005, l'ex-épouse du recourant a imputé sa volonté de mettre fin à l'union conjugale au caractère insupportable pour elle des voyages professionnels de son époux. Il ressort par ailleurs de l'attestation de l'employeur du recourant datée du 2 décembre 2004 que l'intéressé a effectué trois "missions à l'étranger" entre 2002 et 2003, la première ayant eu lieu du 15 juillet 2002 au 20 septembre 2002, la deuxième du 1er au 28 octobre 2002 et la dernière en juillet 2003. Cela étant, l'ex-épouse du recourant ne convainc pas lorsqu'elle explique qu'elle a voulu quitter son mari parce qu'elle s'est lassée du fait qu'il était "souvent absent de la maison pour de longues périodes (raisons professionnelles)". En effet, au jour du dépôt de la requête de séparation, le 28 septembre 2002, le recourant n'avait effectué qu'une "mission à l'étranger". On peut donc admettre que ce déplacement professionnel n'est pas l'unique cause de la rupture et que la dégradation du couple est le fruit d'un processus plus long dans lequel sont intervenus d'autres facteurs.
Certes, comme le relève le recourant, le Tribunal administratif fédéral ne pouvait pas déduire des déclarations de son ex-épouse que la séparation était liée aux problèmes de nature psychologique rencontrés par celle-ci depuis de nombreuses années. Il n'en demeure pas moins que la thèse de la dégradation progressive emporte davantage la conviction que celle de la rupture soudaine, le recourant n'apportant aucun élément probant à l'appui de cette dernière version. Au demeurant, les déclarations de l'ex-épouse du recourant permettent de retenir que la rupture ne s'est pas faite du jour au lendemain. Lors de son audition du 24 mars 2005, elle a en effet expliqué ce qui suit: "peu à peu l'entente au sein du couple se détériorait" et "petit à petit les liens entre nous se sont distendus", ce qui a difficilement pu échapper au recourant. De même, il convient de rappeler que l'un des motifs cités par les intéressés à l'appui de leur requête de séparation du 28 septembre 2002 est la "mésentente quotidienne".
Pour le surplus, le recourant se borne à citer longuement et à plusieurs reprises les déclarations de son ex-épouse, sans alléguer d'autres éléments relatifs aux circonstances de la rupture de leur union. Il y a donc lieu de constater avec l'autorité intimée qu'il n'a pas rendu vraisemblable la survenance d'un événement extraordinaire susceptible d'expliquer une détérioration rapide du lien conjugal au sens de la jurisprudence susmentionnée. Il ne convainc pas davantage lorsqu'il prétend qu'il n'avait pas conscience des difficultés rencontrées par son couple au moment de la signature de la déclaration commune et de l'octroi de la naturalisation facilitée. Même si l'on peut admettre que le recourant ne savait pas tout ce que ressentait son ex-épouse, il ne pouvait pas totalement ignorer l'éloignement progressif de celle-ci et la détérioration de leur relation conjugale. D'ailleurs, même si l'ex-épouse du recourant mentionne que ce dernier n'était pas "trop d'accord" pour la séparation, c'est bien une requête commune qui a été déposée. De plus, le recourant étant rentré de son voyage professionnel le 20 septembre 2002 et la demande de séparation ayant été signée le 28 septembre 2002, il faut bien admettre qu'il a été facile à convaincre et il n'apparaît guère plausible qu'il ait découvert la dégradation de son couple à ce moment-là seulement.
En définitive, il y a lieu de constater que le recourant n'est pas parvenu à renverser la présomption de fait fondée sur l'enchaînement rapide des événements, de sorte que le Tribunal administratif fédéral n'a pas violé l'art. 41 al. 1 LN en confirmant l'annulation de la naturalisation facilitée.
6. 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 fr., 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 ainsi qu'à la Cour III du Tribunal administratif fédéral.
Lausanne, le 8 juillet 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener