Faits: A. A._ - ressortissant nigérian né en 1972, devenu X_ lorsque la Direction cantonale de l'état civil du canton de Genève l'a autorisé à changer de prénoms par arrêté du 26 mars 2007 - est arrivé en Suisse en janvier 1997 et y a déposé une demande d'asile. Le 4 septembre 1997, 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é. Le 6 mars 1998, le prénommé a épousé B._, ressortissante suisse née en 1968. Aucun enfant n'est issu de cette union. En raison de ce mariage, A._ a obtenu une autorisation de séjour dans le canton du Valais pour vivre auprès de son épouse. Le 4 février 2002, 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 octobre 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. L'attention du requérant a en outre été attirée sur le fait que la naturalisation facilitée ne pouvait être octroyée lorsque, avant ou pendant la procédure de naturalisation, l'un des conjoints demandait le divorce ou la séparation ou que la communauté conjugale effective n'existait pas. Si cet état de fait était dissimulé, la naturalisation facilitée pouvait ultérieurement être annulée, conformément au droit en vigueur. Par décision du 17 janvier 2003, l'Office fédéral compétent a accordé la naturalisation facilitée à A._. B. Par courrier du 21 avril 2006, le Service de l'état civil et des étrangers du canton du Valais a informé l'Office fédéral compétent du fait que l'intéressé lui avait demandé de transcrire dans ses registres la naissance de ses deux enfants nés aux Etat-Unis d'Amérique les 13 septembre 2002 et 11 septembre 2005. Ces enfants sont issus de la relation de A._ avec C._, citoyenne d'origine nigériane née le 4 avril 1971. Le Service de l'état civil mentionnait également que le divorce des époux A._ et B._ avait déjà été prononcé le 10 décembre 2003 par le Tribunal de Nyon et que l'intéressé était sur le point d'entreprendre des démarches auprès de l'état civil de Genève pour épouser la mère de ses deux enfants. A._ s'est déterminé sur les faits précités et B._ a été entendue le 18 décembre 2006. Par décision du 25 avril 2007, l'ODM a prononcé l'annulation de la naturalisation facilitée, avec l'assentiment des autorités compétentes du canton du Valais. 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 la déclaration commune 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 et d'une dissimulation de faits essentiels. C. A._ a recouru contre cette décision auprès du Tribunal administratif fédéral. Il a souligné que la volonté de divorcer émanait de B._, que l'enfant né hors mariage n'était pas "programmé" et qu'il n'avait alors pas l'intention d'épouser la mère de celui-ci. Par arrêt du 11 mai 2009, 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 démarches pour se remarier avec une compatriote plus jeune, mère de ses deux enfants - fondait la présomption que le premier mariage de l'intéressé avait pour but prépondérant de s'installer en Suisse et d'obtenir la naturalisation. A._ n'avait pas pu rendre vraisemblable la survenance d'un événement extraordinaire permettant d'expliquer la dégradation rapide du lien conjugal et il n'était pas parvenu à renverser la présomption susmentionnée. D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler cet arrêt. Il se plaint d'arbitraire (art. 9 Cst.) 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). 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 14 juillet 2009, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif formulée par A._. 