Faits:
A. Y._, ressortissante suisse et iranienne, et X._, de nationalité suisse, se sont rencontrés dans le courant de l'année 1994, alors qu'ils étaient tous deux mariés, et ont fait ménage commun dès 1995. Y._ a divorcé le 9 novembre 1995, X._ le 11 avril 2002.
A l'occasion d'un voyage en Iran, les intéressés ont contracté à Téhéran, le 6 mars 2005, un « mariage provisoire légitime sigheh » (ci-après: mariage « sigheh ») d'une durée de cinquante ans. L'acte émis à cette occasion (ci-après: l'acte de mariage n° 1), rédigé en langue persane et comportant la photographie et la signature des comparants, a été enregistré le même jour dans un office notarial.
De retour à Genève, Y._ et X._ se sont séparés le 24 mai 2005. Au début du mois de juin 2005, Y._ a sollicité de la Direction de l'état civil du canton de Genève (ci-après: la Direction de l'état civil) l'enregistrement du mariage célébré le 6 mars 2005. Elle a produit un avis de l'Institut suisse de droit comparé du 23 mai 2005 selon lequel un tel mariage pouvait être reconnu en Suisse, à l'exception de sa limite temporelle. Le 28 juin 2005, l'Office fédéral de l'état civil s'est rallié à l'avis exprimé par l'Institut suisse de droit comparé. Il a invité l'Ambassade de Suisse en Iran à légaliser l'acte de mariage et la Direction de l'état civil à reconnaître le mariage « sigheh », sans limite dans le temps.
Le 9 mars 2006, Y._ a transmis à la Direction de l'état civil un nouvel acte de mariage (ci-après: l'acte de mariage n° 2), établi sur la base de l'acte de mariage n° 1 mais dépourvu de signatures, dûment légalisé par la représentation diplomatique suisse à Téhéran. Se fondant sur les deux actes de mariage produits, la Direction de l'état civil a ordonné la transcription dans les registres suisses de l'état civil du mariage contracté le 6 mars 2005. En avril et mai 2006, X._ est intervenu à plusieurs reprises auprès de la Direction de l'état civil aux fins de faire radier cet enregistrement du mariage.
Par décision du 9 mai 2006, le Département des Institutions du canton de Genève, en sa qualité d'autorité de surveillance de l'état civil, a rejeté la requête de radiation de la transcription du mariage de X._. Il a confirmé que le mariage contracté le 6 mars 2005 à Téhéran était valable en droit suisse, qu'il n'était pas contraire à l'ordre public suisse à condition d'être transcrit sans limitation temporelle et qu'il ne pouvait être annulé que par un jugement.
B. Saisi d'un recours de X._ contre la décision précitée, le Tribunal administratif du canton de Genève l'a rejeté par arrêt du 28 avril 2009, communiqué aux parties le 11 mai suivant. Il a retenu en substance que le mariage « sigheh » était suffisant en Iran pour créer un statut marital, que cette forme de mariage était reconnue en droit musulman chiite, qu'elle était expressément prévue par le code civil iranien, que seule la clause limitant dans le temps les effets de cette institution était contraire à l'ordre public suisse et que, sous cette réserve, la transcription d'un tel mariage dans les registres suisses de l'état civil était possible. Pour le surplus, les conditions fixées pour la transcription avaient été respectées. Aucune des parties n'avait invoqué l'existence d'une cause absolue d'annulation du mariage. L'allégation de X._ selon laquelle il n'avait pas eu l'intention d'épouser Y._ le 6 mars 2005 ne constituait qu'une cause relative d'annulation du mariage, qui relevait de la compétence du juge civil. En outre, la plainte déposée par X._ pour escroquerie et faux dans les titres avait été classée, décision qui avait été confirmée par la Chambre d'accusation du canton de Genève. Enfin, X._ n'avait pas intenté d'action en Iran aux fins de faire constater que, comme il le prétendait, l'acte litigieux du 6 mars 2005 n'était pas valable selon le droit iranien.
C. Par acte du 11 juin 2009 intitulé « recours en matière de droit public », X._ s'est adressé au Tribunal fédéral, le requérant préalablement de définir les termes « mariage valablement célébré à l'étranger » au sens de l'art. 45 al. 1 de la loi fédérale sur le droit international privé du 18 décembre 1987 (LDIP; RS 291) et, principalement, d'annuler l'arrêt du Tribunal administratif cantonal, de renvoyer la cause à cette autorité pour nouvelle décision, d'ordonner l'ouverture d'une enquête sur la validité du mariage du 6 mars 2005 du point de vue iranien et de réserver la décision des autorités judiciaires iraniennes à cet égard. Le recourant se plaint d'une application erronée de l'<ref-law>, d'une constatation arbitraire des faits et de la violation de son droit d'être entendu.
Le Tribunal administratif cantonal a renoncé à déposer une réponse.
Y._ conclut au rejet du recours et sollicite l'assistance judiciaire pour la procédure fédérale.

Considérant en droit:
1. 1.1 L'intitulé erroné ("recours en matière de droit public") du mémoire n'entraîne aucun préjudice pour le recourant, pour autant que les conditions de recevabilité du recours qui serait ouvert soient réunies (<ref-ruling> consid. 1.2 p. 382 et les arrêts cités).
1.2 Le recours vise une décision concernant la radiation d'une inscription au registre de l'état civil au sens de l'<ref-law>. Portant sur la tenue du registre de l'état civil, une telle décision est sujette au recours en matière civile en vertu de l'art. 72 al. 2 let. b ch. 2 LTF (<ref-ruling> consid. 1.1; arrêt 5P.338/2004 du 31 mai 2005 consid. 1.1).
Interjeté en temps utile (<ref-law>) et dans les formes requises (<ref-law>) contre un arrêt final (<ref-law>) rendu par une autorité cantonale de dernière instance (<ref-law>), le recours est recevable en principe comme recours en matière civile. Le recourant a par ailleurs qualité pour recourir (<ref-law>).
1.3 Le recours en matière civile peut être formé pour violation du droit fédéral (<ref-law>), lequel englobe les droits constitutionnels (<ref-ruling> consid. 3.1 p. 447, 462 consid. 2.3 p. 466). Le Tribunal fédéral applique le droit d'office (<ref-law>), sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut ainsi admettre le recours pour d'autres motifs que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 2.2 p. 550). Compte tenu des exigences de motivation posées à l'<ref-law>, le Tribunal fédéral n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une juridiction de première instance, toutes les questions juridiques pouvant se poser lorsqu'elles ne sont plus discutées devant lui (<ref-ruling> consid. 1.2 p. 152).
2. 2.1 Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influencer le sort de la cause (art. 97 al. 1 in fine LTF). Le recourant qui soutient que les faits ont été établis d'une manière manifestement inexacte (<ref-law>), à savoir arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.2.2 p. 252), doit démontrer, par une argumentation précise, en quoi consiste la violation; le Tribunal fédéral n'examine, en effet, la violation de l'interdiction de l'arbitraire que si un tel grief a été invoqué et motivé par le recourant (<ref-law>), c'est-à-dire s'il a été expressément soulevé et exposé de façon claire et détaillée (<ref-ruling> consid. 2.2 p. 246; <ref-ruling> consid. 3.1 p. 399), les exigences de motivation de l'acte de recours correspondant à celles de l'ancien art. 90 al. 1 let. b OJ (<ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 1.4.2 p. 254); les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 4.1 p. 589; 589 consid. 2 p. 591/592 et les arrêts cités). Le recourant ne saurait en outre se contenter de renvoyer aux actes cantonaux ou de reproduire la motivation déjà présentée dans la procédure cantonale: l'<ref-law> exige qu'il discute au moins de manière succincte les considérants de la décision attaquée (<ref-ruling> consid. 2.1-2.3 p. 245/247; <ref-ruling> consid. 3.1 p. 399/400 et la jurisprudence citée).
Quant à l'appréciation des preuves et à la constatation des faits, le Tribunal fédéral se montre réservé, vu le large pouvoir qu'il reconnaît en la matière aux autorités cantonales (<ref-ruling> consid. 4b p. 40; <ref-ruling> consid. 9 p. 399 et les arrêts cités). Il n'intervient, du chef de l'art. 9 Cst., en relation avec les art. 97 al. 1 et 105 al. 2 LTF, que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, a omis sans raisons objectives de tenir compte de preuves pertinentes ou a opéré, sur la base des éléments recueillis, des déductions insoutenables (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 4.3 p. 62).
2.2 Le recourant a annexé à son mémoire de recours un jugement par défaut du 6 juin 2009 de la 5ème Chambre du Tribunal général de Téhéran ordonnant l'annulation de la mention du mariage dans une pièce d'identité de l'intimée.
Cette pièce nouvelle est postérieure à la date de l'arrêt attaqué et ne peut par conséquent pas être prise en considération (<ref-law>). Il s'ensuit que les conclusions du recourant tendant à ordonner l'ouverture d'une enquête portant sur la validité du mariage du 6 mars 2005 du point de vue du droit iranien et à réserver la décision des autorités judiciaires iraniennes à cet égard sont irrecevables dans la mesure où elles se fondent sur ladite pièce nouvelle.
3. Se référant à l'<ref-law>, selon lequel un mariage valablement célébré à l'étranger est reconnu en Suisse, le recourant fait valoir que le Tribunal administratif a arbitrairement privilégié l'examen de la question de savoir si, abstraitement, un mariage « sigheh » pouvait être reconnu en Suisse, après correction à l'aune de l'ordre public suisse, plutôt que de déterminer en priorité si, concrètement, l'acte de mariage du 6 mars 2005 faisait réellement des intéressés des époux du point de vue du droit iranien. En rejetant sa thèse selon laquelle cet acte était sans valeur du point de vue du droit étranger, le Tribunal administratif aurait constaté arbitrairement les faits au sens de l'art. 9 Cst., méconnu son obligation d'établir d'office la teneur du droit étranger selon l'<ref-law> et violé le droit d'être entendu du recourant concernant des éléments de fait déterminants à teneur de l'art. 29 al. 2 Cst.
3.1 Le recourant reproche à cet égard au Tribunal administratif d'avoir arbitrairement tenu pour établi que le mariage célébré le 6 mars 2005 avait fait l'objet d'une inscription dans le registre des mariages du bureau notarial n° 78, alors qu'il avait établi par pièce que le numéro d'inscription 3413 figurant dans l'acte de mariage n° 2 indiquait, sous cette référence, le mariage d'un autre couple.
Cette critique ne saurait être retenue. Il ressort en effet d'une attestation du notaire en charge de l'office public n° 78 que le document produit par le recourant fait état d'un mariage du type « aghd » (mariage sans limitation dans le temps), au demeurant célébré le 29 janvier 2006, alors que le numéro d'inscription 3413 attribué aux parties correspond à un numéro des registres des mariages « sigheh ». C'est donc sans arbitraire que le Tribunal administratif a retenu que le mariage célébré le 6 mars 2005 avait été dûment inscrit dans le registre des mariages « sigheh ». Cette inscription est d'ailleurs confirmée dans un document d'état civil produit au dossier, soit un « shenasnameh », correspondant à la fois à une carte d'identité et à l'équivalent d'un certificat de naissance.
3.2 Au dire du recourant, le Tribunal administratif aurait également fait preuve de partialité dans l'établissement des faits en omettant de mentionner le contenu d'un passage recouvert au correcteur liquide d'un document produit par l'intimée le 28 mars 2007, soit l'attestation de l'existence du mariage célébré le 6 mars 2005, établie à la suite de la perte de l'original de l'acte de mariage n°1. Selon lui, le passage en question mentionnait que le document n'avait pas été enregistré au registre des mariages et l'utilisation du correcteur ne pouvait qu'être le fait de l'intimée.
Il peut paraître surprenant qu'à l'occasion de la brève consultation de l'original du document en cause, le 19 juillet 2007, dans les locaux du Tribunal administratif, le traducteur-juré mandaté par le recourant soit parvenu à déchiffrer le contenu du passage occulté, tant le correcteur utilisé masque efficacement le texte. A supposer que celui-ci fasse vraiment état d'une absence d'enregistrement, le Tribunal administratif pouvait s'abstenir de faire procéder à des investigations complémentaires pour tenter d'en préciser la teneur et de déterminer l'auteur de l'utilisation du correcteur liquide: en effet, il est vraisemblable, d'une part, que ce n'est pas le document incriminé qui a été enregistré mais bien l'original de l'acte de mariage n° 1; d'autre part, il est établi par pièce que le mariage célébré le 6 mars 2005 a bien été inscrit dans le registre des mariages « sigheh ».
Les faits, tels que retenus sur ce point dans l'arrêt attaqué, ne révèlent ni arbitraire ni partialité de la part du Tribunal administratif.
4. Le recourant invoque également l'établissement arbitraire des faits de la cause résultant de la violation formelle de son droit d'être entendu. Il se plaint à cet égard du refus que lui a opposé le Tribunal administratif de verser au dossier l'écriture spontanée qu'il a produite le 26 juin 2008 et d'ordonner un second échange d'écritures au sens de l'art. 74 de la loi genevoise du 12 septembre 1985 sur la procédure administrative (LPA/GE).
4.1 Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend notamment pour le justiciable le droit de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, d'obtenir l'administration des preuves pertinentes et valablement offertes, de participer à l'administration des preuves essentielles et de se déterminer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.1; <ref-ruling> consid. 2a/aa; <ref-ruling> consid. 3a).
Le juge peut cependant renoncer à l'administration de certaines preuves, notamment lorsque les faits dont les parties veulent rapporter l'authenticité ne sont pas importants pour la solution du litige. Ce refus d'instruire ne viole leur droit d'être entendues que si l'appréciation anticipée de la pertinence du moyen de preuve offert, à laquelle le juge a ainsi procédé, est entachée d'arbitraire (<ref-ruling> consid. 3 et les arrêts cités). L'arbitraire prohibé par l'art. 9 Cst. ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral ne s'écarte de la solution retenue en dernière instance cantonale que si elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté ou si elle heurte de manière choquante le sentiment de la justice ou de l'équité. Il ne suffit pas que la motivation de la décision soit insoutenable; encore faut-il qu'elle soit arbitraire dans son résultat (<ref-ruling> consid. 5.1; <ref-ruling> consid. 2.1, 57 consid. 2; <ref-ruling> consid. 3.1).
Le droit d'être entendu comprend en principe aussi le droit de répliquer (<ref-ruling>, 100; <ref-ruling>). Lorsque le droit de procédure applicable ne prévoit pas de communication de la prise de position, l'autorité doit informer la partie du dépôt de celle-ci et de la possibilité de se déterminer à son sujet. S'il ne prévoit en principe qu'un seul échange d'écritures, l'autorité peut se limiter dans un premier temps à communiquer la prise de position à titre d'information, sans avis formel de la possibilité de répliquer; la partie est ainsi mise en situation de faire ou non usage de cette possibilité; si elle s'en abstient, elle est censée y avoir renoncé (ATF <ref-ruling> consid. 3.3.3). Selon l'art. 74 LPA/GE, « la juridiction peut autoriser une réplique et une duplique si ces écritures sont estimées nécessaires ». En droit cantonal, l'opportunité d'un second échange d'écritures est ainsi laissée à l'appréciation de l'autorité de jugement, qui peut décider que les éléments de fait et de droit résultant d'un premier échange d'écritures sont suffisants pour lui permettre de se prononcer. Selon la jurisprudence, lorsque l'autorité n'a pas - ou pas suffisamment - motivé sa décision et n'a indiqué en détail les motifs de cette décision que dans sa réponse, l'autorité de recours viole le droit d'être entendu en refusant de transmettre au recourant cette réponse pour qu'il puisse répliquer (<ref-ruling> consid. 3). Plus généralement, l'autorité a l'obligation de communiquer au recourant les écritures de l'intimé quand celles-ci contiennent des éléments nouveaux et importants au sujet desquels le recourant n'a pas pu prendre position (<ref-ruling> consid. 3 p. 87, 307 consid. 4b p. 314; <ref-ruling> consid. 4a p. 304).
Le droit d'être entendu comprend en principe aussi le droit de répliquer (<ref-ruling>, 100; <ref-ruling>). Lorsque le droit de procédure applicable ne prévoit pas de communication de la prise de position, l'autorité doit informer la partie du dépôt de celle-ci et de la possibilité de se déterminer à son sujet. S'il ne prévoit en principe qu'un seul échange d'écritures, l'autorité peut se limiter dans un premier temps à communiquer la prise de position à titre d'information, sans avis formel de la possibilité de répliquer; la partie est ainsi mise en situation de faire ou non usage de cette possibilité; si elle s'en abstient, elle est censée y avoir renoncé (ATF <ref-ruling> consid. 3.3.3). Selon l'art. 74 LPA/GE, « la juridiction peut autoriser une réplique et une duplique si ces écritures sont estimées nécessaires ». En droit cantonal, l'opportunité d'un second échange d'écritures est ainsi laissée à l'appréciation de l'autorité de jugement, qui peut décider que les éléments de fait et de droit résultant d'un premier échange d'écritures sont suffisants pour lui permettre de se prononcer. Selon la jurisprudence, lorsque l'autorité n'a pas - ou pas suffisamment - motivé sa décision et n'a indiqué en détail les motifs de cette décision que dans sa réponse, l'autorité de recours viole le droit d'être entendu en refusant de transmettre au recourant cette réponse pour qu'il puisse répliquer (<ref-ruling> consid. 3). Plus généralement, l'autorité a l'obligation de communiquer au recourant les écritures de l'intimé quand celles-ci contiennent des éléments nouveaux et importants au sujet desquels le recourant n'a pas pu prendre position (<ref-ruling> consid. 3 p. 87, 307 consid. 4b p. 314; <ref-ruling> consid. 4a p. 304).
4.2 4.2.1 Par courrier du 26 juin 2008, le recourant a informé le Tribunal administratif de ce qu'il avait saisi les autorités judiciaires iraniennes d'une requête devant lui permettre d'accéder au registre d'état civil de Téhéran et que les documents qu'il avait ainsi obtenus démontraient que l'intimée n'était pas mariée. Le Tribunal administratif lui a retourné ce courrier et ses annexes, en précisant que les écritures spontanées n'étaient pas admises.
Le Tribunal administratif était fondé à agir de la sorte dès lors qu'il avait averti les parties, le 13 février 2008, qu'aucune correspondance ou production de pièces ne serait admise jusqu'à droit jugé après la production de l'écriture du recourant agendée au 28 février 2008. Pour le surplus, les pièces produites par le recourant le 26 juin 2008 étaient constituées d'un acte de naissance de l'intimée, sans indication concernant son état civil, et de l'attestation de l'absence d'enregistrement du mariage dans le registre des mariages du type « aghd » (cf. consid. 3.1 ci-dessus), soit d'un fait dont le tribunal avait déjà connaissance. Ces pièces n'étaient donc pas de nature à prouver l'allégation du recourant selon laquelle l'intimée était considérée comme célibataire au sens du droit iranien.
Le refus du Tribunal administratif de verser ces documents au dossier ne constituait donc pas une violation du droit d'être entendu du recourant.
4.2.2 Le recourant se plaint également du refus opposé par le Tribunal administratif à ses différentes requêtes tendant au dépôt d'une réplique. Le 26 juillet 2006, il a requis de pouvoir répliquer aux observations du département cantonal; le 15 août 2006, il a sollicité la faculté de se déterminer sur certaines pièces versées au dossier par l'intimée; enfin, le 31 octobre 2006, il a réitéré sa requête, l'assortissant d'une demande d'expertise relative au décollement des timbres officiels et à la contre-façon de sa signature sur un document produit par l'intimée. Plutôt que d'ordonner un second échange d'écritures, la juge déléguée du Tribunal administratif a appointé la tenue d'une audience de comparution personnelle des parties, qu'elle a fixée au 1er décembre 2006. Simultanément, elle a ordonné la production, par le département cantonal et par l'intimée, d'un certain nombre de pièces originales destinées à vérifier la validité de la transcription du mariage litigieux en Iran et dans les registres de l'état civil cantonal.
Le 10 novembre 2008, le Tribunal administratif a adressé une copie des pièces produites par le département cantonal au recourant. Ce dernier a bénéficié de la possibilité de se déterminer sur ces documents et, d'une manière plus générale, sur les écritures des autres parties lors de l'audience du 1er décembre 2006. Au cours de celle-ci, il a eu l'occasion de verser au dossier de nouvelles traductions de certaines pièces produites par l'intimée. La pièce originale de l'acte de mariage n° 1, dont la production par l'intimée a été ordonnée à l'issue de l'audience de comparution personnelle des parties, a été versée au dossier, en copie, le 28 mars 2007 et, dans sa version originale, le 16 juillet 2007. Le recourant a pu se déterminer, respectivement les 2 mai et 19 juillet 2007, sur chacune de ces productions. Enfin, suite à la production par l'intimée du « shenasnameh » sous forme de photocopie le 10 décembre 2007, de traduction certifiée conforme le 7 février 2008 et d'original le 28 mars 2008, le recourant a pu présenter ses observations, ce qu'il a fait à teneur d'un courrier du 28 février 2008, accompagné de pièces. Ce courrier a été enregistré par le Tribunal administratif comme une écriture, même si elle n'a pas été formellement désignée par le terme de réplique.
Le Tribunal administratif a donc donné suite à toutes les réquisitions présentées par le recourant les 26 juillet, 15 août et 31 octobre 2006, à l'exception de la requête tendant à la mise en oeuvre d'une expertise concernant l'authenticité de l'acte de mariage n° 2 produit par l'intimée. Bien que le recourant ne s'en plaigne pas devant le Tribunal fédéral, il faut constater que ce refus était justifié au regard de l'issue réservée à la plainte pénale déposée par le recourant le 7 juin 2006 à l'encontre de l'intimée pour escroquerie et faux dans les titres. Cette plainte, qui reprenait l'ensemble des faits contenus dans le recours déposé auprès du Tribunal administratif, a fait l'objet d'une ordonnance de classement de la part du Procureur général du canton de Genève le 24 juillet 2006, confirmée sur recours par la Chambre d'accusation le 17 octobre 2006. Selon l'autorité pénale, la prévention de faux dans les titres, qui concernait notamment l'acte de mariage n° 2, n'était pas établie. Le Tribunal administratif était dès lors fondé à renoncer à la mesure d'instruction sous forme d'expertise requise par le recourant.
Le Tribunal administratif n'a par conséquent pas abusé de son pouvoir d'appréciation en refusant d'ordonner un second échange d'écritures formel au sens de l'art. 74 LPA/GE. En effet, les éléments de fait et de droit résultant du premier échange d'écritures, de l'audience de comparution personnelle des parties, des pièces versées au dossier postérieurement à cette audience et de l'écriture du recourant du 28 février 2008 étaient suffisants pour qu'il puisse se prononcer sur tous les aspects de la cause.
4.2.3 C'est en vain que le recourant critique l'appréciation du Tribunal administratif selon laquelle il n'avait pas contesté l'existence de deux types de registres matrimoniaux, l'un pour les mariages ordinaires, l'autre pour les mariages « sigheh », au motif qu'il a été privé de la possibilité de répliquer. Il pouvait parfaitement le faire dans son écriture du 28 février 2008, qu'il a essentiellement consacrée à la critique de l'authenticité et de la traduction du « shenasnameh » produit par l'intimée.
C'est en vain également qu'il reproche au Tribunal administratif d'avoir retenu qu'il n'avait pas intenté action en Iran pour obtenir des autorités compétentes la constatation de l'invalidité de l'acte de mariage litigieux selon le droit iranien. En effet, le courrier du 26 juin 2008, dont il se plaint qu'il lui a été retourné au titre d'écriture non requise, faisait uniquement état d'une requête d'accession au registre d'état civil de Téhéran (cf. consid. 4.2.1 ci-dessus); en outre, les documents qu'il s'était ainsi procurés démontraient uniquement l'inexistence d'un mariage de type « aghd » et non d'un mariage « sigheh » (ibidem).
4.2.4 Le recourant fait encore grief au Tribunal administratif d'avoir mentionné dans l'arrêt attaqué qu'il n'avait pas formulé d'observations après la production du « shenasnameh » original, en particulier qu'il n'avait pas soutenu qu'il pût s'agir d'un faux. S'il est exact que le recourant ne s'est pas manifesté après la consultation du document original - alors qu'il s'est empressé de réagir lors de toute autre production de pièces de la part de l'intimée -, il avait cependant formulé un certain nombre de remarques critiques dans son écriture du 28 février 2008 au sujet de la photocopie et du duplicata de la traduction de cette pièce, qui avaient été versés au dossier antérieurement. Il avait notamment invoqué certaines divergences formelles entre la traduction produite et celle effectuée par le traducteur-juré qu'il avait consulté. Il n'est en outre pas certain que le dépôt d'observations non sollicitées aurait été agréé par le Tribunal administratif, comme l'a démontré le renvoi à son expéditeur du courrier du recourant du 26 juin 2008. Si la mention de l'absence de réaction du recourant peut paraître discutable, il faut constater qu'elle n'est pas déterminante pour l'issue du litige. En effet, le « shenasnameh » original faisait clairement état du mariage de l'intimée et du recourant le 6 mars 2005 devant l'office notarial n° 78 de Téhéran.
4.2.5 Le recourant soutient enfin que le Tribunal administratif a fait preuve de légèreté en écartant la prévention d'usage de faux dans les titres à l'encontre de l'intimée au motif qu'il n'avait fourni aucun élément inconnu du juge pénal et qu'il n'avait pas contesté l'appréciation de celui-ci.
S'il est vrai que l'ordonnance de la Chambre d'accusation ne pouvait pas faire l'objet d'un recours au Tribunal fédéral, le Tribunal administratif pouvait se fonder sur l'appréciation du juge pénal quant à la réalité du délit de faux dans les titres dénoncé par le recourant, dès lors que les faits invoqués à l'appui de la plainte pénale étaient identiques à ceux allégués devant le Tribunal administratif. Quant aux explications fournies lors de l'audience du 1er décembre 2006 par l'intimée au sujet des circonstances de l'établissement de l'acte de mariage n° 2, que le recourant assimile au consentement à l'élaboration d'un faux dans les titres, elles démontrent que l'intéressée s'est contentée de fournir certaines indications à l'auteur du document, précisément pour éviter l'accusation de faux dans les titres.
Les critiques du recourant sur ce point sont donc infondées.
5. Vu ce qui précède, le recours doit être rejeté dans la mesure de sa recevabilité.
Dès lors qu'il succombe, le recourant doit supporter les frais judiciaires (<ref-law>) et verser une indemnité à titre de dépens à l'intimée (<ref-law>). Dans ces conditions, la requête d'assistance judiciaire présentée par celle-ci devient sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Une indemnité de 2'000 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
4. La requête d'assistance judiciaire présentée par l'intimée est sans objet.
5. Le présent arrêt est communiqué aux parties, au Tribunal administratif et au Département des Institutions du canton de Genève.
Lausanne, le 5 novembre 2009
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Le Greffier:
Hohl Fellay