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. 