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._.

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. Le recourant se plaint d'arbitraire dans l'interprétation des preuves et des faits et il présente son propre exposé des faits qu'il juge pertinents. Il perd ainsi de vue que 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; pour une définition de l'arbitraire cf. <ref-ruling> consid. 3.1 p. 265 s.; <ref-ruling> consid. 3.1 p. 153), ce qu'il lui appartient de démontrer par une argumentation répondant aux exigences de l'<ref-law>, respectivement de l'<ref-law> (<ref-ruling> consid. 1.4.3 p. 254 s.). Une telle démonstration faisant défaut en l'espèce, il n'y a pas lieu de s'écarter des faits retenus dans la décision attaquée.
3. L'argumentation du recourant consiste en substance à contester l'annulation de la naturalisation facilitée en application de l'art. 41 LN.
3.1 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. 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). 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).
3.2 En l'occurrence, la présomption de fait n'est pas véritablement discutée par le recourant. Elle peut du reste effectivement se fonder sur un 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), le dépôt de la requête de divorce étant en outre intervenu seulement cinq mois après l'octroi de la naturalisation facilitée. 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é.
Le Tribunal administratif fédéral a estimé que cette présomption était renforcée par le fait que le recourant avait eu un enfant hors mariage, ce que son ex-épouse ignorait. Celle-ci avait d'ailleurs déclaré qu'elle n'aurait jamais signé la déclaration du 10 octobre 2002 si elle avait eu connaissance de ce fait. Les explications de l'intéressé sur le caractère "accidentel" de la conception de cet enfant étaient contredites par la naissance d'un deuxième enfant issu de la même relation, ainsi que par les démarches du recourant pour épouser la mère des enfants en question. Le recourant avait donc mené une véritable double vie, ce qui était incompatible avec la notion de vie commune voulue par l'art. 27 LN. De plus, il n'avait pas rendu vraisemblable la survenance d'un événement extraordinaire susceptible d'expliquer une détérioration rapide du lien conjugal après la signature de la déclaration de vie commune en octobre 2002 ou l'octroi de la naturalisation en janvier 2003, les problèmes conjugaux importants remontant déjà au mois d'avril 2002. Enfin, en omettant de révéler la naissance de son premier enfant le 13 septembre 2002, le recourant avait dissimulé à l'ODM un fait essentiel, susceptible d'avoir une incidence sur la décision d'octroi de la naturalisation facilitée. Cette décision pouvait donc être annulée pour ce motif également.
Le recourant ne remet pas en cause ce dernier point et il ne critique pas l'appréciation du Tribunal administratif fédéral de manière convaincante. Il se borne en effet à présenter sommairement sa propre appréciation des événements et à affirmer que la communauté conjugale était stable en octobre 2002, ce qui est contredit par les éléments retenus par l'arrêt attaqué. Il prétend en outre que la naissance de son premier enfant hors mariage ne remettait pas en cause cette communauté conjugale, mais il ne démontre aucunement cette assertion. Le recourant évoque également les incompatibilités qui sont apparues au sein de son couple "comme dans le cadre de bien des ménages" et il reproche implicitement au Tribunal administratif fédéral d'en avoir déduit que son union n'était pas effective et stable. Il est vrai que certaines affirmations contenues dans l'arrêt attaqué sont discutables, notamment celles relatives à "l'expérience générale" en matière de "processus prolongé de dégradation des rapports conjugaux, en principe entrecoupé de tentatives de réconciliation". En effet, même si le Tribunal fédéral a parfois mentionné ces critères par le passé, on peut difficilement admettre l'établissement de règles générales dans ce domaine (cf. arrêt 1C_42/2009 du 14 mai 2009 consid. 3.2.2). Cet élément n'est cependant pas déterminant en l'espèce, vu l'enchaînement des événements fondant la présomption de fait et l'absence d'éléments probants susceptibles de la renverser. Pour le surplus le recourant ne présente aucun argument susceptible de contredire le raisonnement du Tribunal administratif fédéral. Il peut donc être renvoyé aux considérants de l'arrêt attaqué, qui exposent clairement les motifs ayant conduit à l'annulation de la naturalisation facilitée.
4. 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é à la mandataire du recourant, à l'Office fédéral des migrations et au Tribunal administratif fédéral, Cour III.
Lausanne, le 8 septembre 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener