Faits:
A. A.a Le 29 février 1968, l'État X._ (ci-après: le recourant) et la société Z._ (ci-après: l'intimée) ont conclu un accord de participation (Participation Agreement) pour la construction, l'entretien et l'exploitation, sur le territoire du recourant, d'un oléoduc.
L'art. 12 (a) de l'accord de participation contient une clause arbitrale libellée en ces termes:
"If at any time within the period of this Agreement or thereafter, any doubt, difference or dispute shall arise between the Parties concerning the interpretation or execution ot this Agreement or anything connecting therewith or concerning the rights and liabilities of the Parties hereunder, the same shall, failing any agreement to settle it by other means, be referred to arbitration. Each Party shall appoint one arbitrator. If such arbitrators fail to settle the dispute by mutual agreement or to agree upon a Third Arbitrator, the President of the International Chamber of Commerce in Paris shall be requested to appoint such Third Arbitrator. The decision of the Board of Arbitrators so appointed shall be final and binding upon the Parties."
La pièce 5bis, produite par le recourant, propose la traduction française suivante de ladite clause:
"Si, à quelque moment que ce soit pendant la durée du présent Accord ou ultérieurement, un doute, différend ou litige quelconque se produit entre les Parties concernant l'interprétation ou l'exécution de cet Accord ou toute matière y relative, ou concernant les droits et obligations des Parties découlant de cet Accord, et à défaut d'accord sur un autre mode de règlement, ce doute, différend ou litige sera soumis à l'arbitrage. Chaque Partie nommera un arbitre. Si ces arbitres ne règlent pas le litige d'un commun accord, ou s'ils ne se mettent pas d'accord sur le choix d'un Troisième Arbitre, il sera demandé au Président de la Chambre de commerce internationale [CCI] à Paris de nommer ce Troisième Arbitre. La décision du Tribunal arbitral ainsi constitué sera définitive et obligatoire pour les Parties."
A.b Le 14 octobre 1994, l'intimée, se fondant sur cette clause compromissoire, a engagé une procédure arbitrale en désignant son arbitre et en invitant le recourant à nommer le sien. Elle s'est vu opposer une fin de non-recevoir, motifs pris de l'identification insuffisante de l'objet du litige et de l'absence de négociations préalables.
Devant ce refus, l'intimée, par assignation du 22 août 1995, a saisi le président du Tribunal de grande instance de Paris d'une requête en désignation d'arbitre. Econduite dans un premier temps, elle a finalement obtenu gain de cause au terme d'une série de péripéties procédurales qu'il n'est pas nécessaire de relater ici. En effet, statuant le 1er février 2005, la Première Chambre civile de la Cour de cassation française a rejeté les pourvois formés par le recourant contre les arrêts des 29 mars et 8 novembre 2001 par lesquels la Cour d'appel de Paris avait imparti à celui-ci un délai pour choisir un arbitre, puis, faute d'un tel choix, désigné un arbitre à cette partie. Elle a justifié ce rejet en ces termes:
"Mais attendu que l'impossibilité pour une partie d'accéder au juge, fût-il arbitral, chargé de statuer sur sa prétention, à l'exclusion de toute juridiction étatique, et d'exercer ainsi un droit qui relève de l'ordre public international consacré par les principes de l'arbitrage international et l'article 6.1, de la Convention européenne des droits de l'homme, constitue un déni de justice qui fonde la compétence internationale du président du tribunal de grande instance de Paris, dans la mission d'assistance et de coopération du juge étatique à la constitution d'un tribunal arbitral, dès lors qu'il existe un rattachement avec la France; que l'arrêt attaqué ayant relevé que la société Z._ était, en l'état de la jurisprudence de la Cour suprême du recourant, dans l'impossibilité de saisir les tribunaux [du recourant] ou [de l'intimée] pour nommer un arbitre à la place [du recourant] qui s'y refusait, dès lors que [le recourant] avait expressément déclaré ne pas reconnaître leur compétence respective pour y procéder, que cette impossibilité était générale et durable, et, enfin, que le lien avec la France, même s'il était ténu, comme résultant du choix par les parties du président de la CCI de Paris pour une désignation éventuelle d'un troisième arbitre, était le seul dont la société Z._ pouvait utilement se prévaloir pour assurer la réalisation de leur commune volonté de recourir à l'arbitrage, la cour d'appel en a exactement déduit que cet état de fait constituait, pour la société Z._, un déni de justice justifiant la compétence internationale du juge français; qu'en jugeant que le président du tribunal de grande instance, en se déclarant incompétent pour statuer, avait méconnu l'étendue de ses pouvoirs et commis ainsi un excès de pouvoir négatif, la cour d'appel a légalement justifié sa décision;"
A.c Nonobstant les pourvois formés devant la Cour de cassation, les deux arbitres ont émis, le 8 octobre 2002, un premier ordre procédural.
Le 24 décembre 2003, l'intimée a déposé un mémoire de demande (Statement of Claim). Elle a conclu à ce que le recourant fût condamné à lui payer, d'une part, quelque 800 millions de dollars, représentant la moitié de la valeur des actifs liés à l'accord de participation de 1968, et, d'autre part, des dommages-intérêts correspondant à la somme dont une société nommée Y._ pourrait être reconnue débitrice à l'issue d'une autre procédure arbitrale pendante.
Dans son mémoire de réponse (Statement of Defence) du 23 avril 2004, le recourant a invité le Tribunal arbitral à se déclarer incompétent du fait de la désignation de son arbitre intervenue en violation de la clause arbitrale. Il a, en outre, mis en cause l'indépendance et l'impartialité de l'arbitre de l'intimée au regard du second chef de la demande de cette dernière. Sur le fond, le recourant a conclu au rejet des deux demandes et, reconventionnellement, à la condamnation de son adverse partie au paiement de dommages-intérêts au titre de la violation de l'accord de participation.
Le 19 juillet 2004, les arbitres ont fixé le siège de l'arbitrage à Genève, après que l'intimée avait accepté, par lettre du 24 décembre 2003, la proposition faite en ce sens le 31 octobre 2003 par le recourant, chacune des parties maintenant d'ailleurs sa position quant à la validité de la désignation de l'arbitre du recourant par les tribunaux français.
Dans le cadre d'un nouvel échange d'écritures, le recourant a persisté dans son objection relative à cette désignation, en dépit du rejet de ses pourvois par la Cour de cassation (cf. let. A.b ci-dessus). De ce fait, les parties et les arbitres sont convenus que la question de la régularité de la composition du Tribunal arbitral serait traitée à titre préalable. Après un premier échange d'écritures, le Tribunal arbitral a tenu, le 18 décembre 2006, une audience de plaidoiries à ce sujet, puis ordonné un nouvel échange d'écritures.
B. Le 10 février 2012, le Tribunal arbitral a rendu une sentence, intitulée Partial Award, au terme de laquelle il a rejeté les objections soulevées par le recourant contre les nominations de son arbitre et de l'arbitre de l'intimée, admettant ainsi la régularité de sa constitution.
Dans sa sentence, le Tribunal arbitral souligne que la première obligation du signataire d'une convention d'arbitrage consiste à désigner un arbitre. Selon lui, l'absence, dans la clause arbitrale litigieuse, d'une disposition supplétive applicable en cas de violation de cette obligation, ne constitue pas une échappatoire, mais confirme le caractère inéluctable d'un tel devoir. Par conséquent, dès lors qu'une partie, à l'instar du recourant, ne désigne pas son arbitre, la partie adverse est habilitée à saisir la juridiction étatique compétente afin de pallier semblable défaillance. Il s'agit là d'une règle appliquée dans de nombreux pays, y compris la Suisse (art. 179 de la loi fédérale sur le droit international privé du 18 décembre 1987 [LDIP]; RS 291). En ce qui concerne le cas concret, les arbitres notent que le recourant a eu l'occasion de développer ses arguments à quatre reprises par-devant les tribunaux français, que le droit d'être entendu de toutes les parties a été largement respecté et que la décision de la Cour d'appel de Paris de désigner un arbitre au recourant, prise pour éviter un possible déni de justice, a été confirmée par la Cour de cassation française. Ils en déduisent que pareille décision, tout à fait valable, ne peut légitimement être remise en cause.

Pour ce qui est de l'indépendance et de l'impartialité de l'arbitre de l'intimée en relation avec le second chef de la demande formée par celle-ci, le Tribunal arbitral considère qu'il n'est pas en mesure d'en juger en l'état, la question étant par trop liée à l'examen du fond de l'affaire.
C. Le 14 mars 2012, le recourant a formé un recours en matière civile, en y invitant le Tribunal fédéral à annuler la sentence du 10 février 2012 et à constater "l'incompétence du collège arbitral constitué dans cette affaire". Il a requis, en outre, l'octroi de l'effet suspensif ainsi que l'anonymisation des noms des parties dans la version de l'arrêt qui sera publiée sur internet et, le cas échéant, au recueil officiel.
Le lendemain, le recourant a déposé une seconde version de son recours, dans laquelle il a apporté quelques retouches au texte initial qu'une panne informatique l'avait empêché de finaliser.
L'effet suspensif a été accordé au recours, à titre superprovisoire, par ordonnance présidentielle du 20 mars 2012.
L'intimée a déposé sa réponse le 7 mai 2012, concluant principalement au rejet du recours et, subsidiairement, à l'irrecevabilité de celui-ci. Elle a requis, de plus, l'octroi d'un délai supplémentaire pour apporter à sa réponse les éventuelles modifications nécessaires au cas où le Tribunal fédéral prendrait en considération le second mémoire du recourant.
Les 30 mai et 18 juin 2012, le recourant et l'intimée ont déposé, respectivement, une réplique et une duplique dans lesquelles ils ont maintenu leurs précédentes conclusions.
Le Tribunal arbitral, qui a produit un bordereau des pièces versées au dossier de l'arbitrage, ne s'est pas déterminé sur le fond du recours.
Considérant en droit:
1. D'après l'<ref-law>, le Tribunal fédéral rédige son arrêt dans une langue officielle, en règle générale dans la langue de la décision attaquée. Lorsque cette décision a été rendue dans une autre langue (ici l'anglais), le Tribunal fédéral utilise la langue officielle choisie par les parties. Devant lui, celles-ci se sont servies toutes deux du français. Aussi convient-il de rendre le présent arrêt dans cette langue.
2. Dans le domaine de l'arbitrage international, le recours en matière civile est recevable contre les décisions de tribunaux arbitraux aux conditions prévues par les art. 190 à 192 LDIP (<ref-law>).
2.1 Le siège de l'arbitrage a été fixé à Genève. L'une des parties au moins (en l'occurrence, les deux) n'avait pas son domicile en Suisse au moment déterminant. Les dispositions du chapitre 12 de la LDIP sont donc applicables (<ref-law>).
Le recours en matière civile est recevable contre les décisions de tribunaux arbitraux aux conditions prévues par les art. 190 à 192 LDIP (<ref-law>). L'acte attaquable peut être une sentence finale, qui met un terme à l'instance arbitrale pour un motif de fond ou de procédure, une sentence partielle, qui porte sur une partie quantitativement limitée d'une prétention litigieuse ou sur l'une des diverses prétentions en cause, voire une sentence préjudicielle ou incidente, qui règle une ou plusieurs questions préalables de fond ou de procédure (sur ces notions, cf. l'<ref-ruling> consid. 1.2.1 p. 757). Pour juger de la recevabilité du recours, ce qui est déterminant n'est pas la dénomination du prononcé entrepris, mais le contenu de celui-ci (<ref-ruling> consid. 2.3.3 p. 205, 597 consid. 4).
Lorsqu'un tribunal arbitral, par une sentence séparée, admet la régularité de sa composition, il rend une décision incidente (<ref-law>). Tel est le cas en l'espèce, bien que la sentence entreprise soit improprement qualifiée de partielle (Partial Award). En vertu de l'<ref-law>, ladite sentence ne pouvait être attaquée devant le Tribunal fédéral que pour les motifs tirés de la composition irrégulière (<ref-law>) ou de l'incompétence (<ref-law>) du Tribunal arbitral. En l'occurrence, seuls ces deux motifs ont été soumis à l'examen de la Cour de céans.
2.2 Le recourant est particulièrement touché par la sentence attaquée, laquelle l'oblige à se soumettre à une juridiction arbitrale dont il conteste la régularité de la composition, de même que la compétence. Aussi a-t-il un intérêt digne de protection à l'annulation de cette sentence, ce qui lui confère la qualité pour recourir (<ref-law>).
2.3 Sans être contredit par l'intimée, le recourant expose que la sentence attaquée lui a été communiquée d'abord par télécopie du 13 février 2012, puis par un courrier recommandé qui est parvenu à ses mandataires le 20 février 2012.
Supposé valable, le premier mode de communication impliquerait que le délai de 30 jours suivant la notification de la sentence finale (<ref-law>), dans lequel le recours devait être adressé au Tribunal fédéral, est arrivé à échéance le 14 mars 2012, si bien que seul le premier mémoire de recours, posté à cette date, aurait été déposé en temps utile, à l'exclusion du second mémoire, posté le lendemain. Dans l'hypothèse inverse, où la notification de ladite sentence par fax n'eût pas fait courir le délai de recours, comme c'est notamment le cas pour les sentences du Tribunal Arbitral du Sport (arrêt 4A_392/2010 du 12 janvier 2011 consid. 2.3.2), le point de départ de ce délai devrait être fixé, en l'espèce, au 21 février 2012, de sorte que le second mémoire de recours aurait été déposé, lui aussi, avant l'expiration du délai précité. On ignore, toutefois, si les parties sont convenues d'un mode de notification spécial, telle la communication de l'original sous pli recommandé, pour les sentences à venir dans l'arbitrage en question.
En tout état de cause, il ressort de la lecture comparée des deux mémoires que le second d'entre eux ne fait, pour l'essentiel, que rectifier certaines erreurs formelles contenues dans le premier et qu'il ne s'apparente ainsi nullement à un recours complémentaire, lequel serait irrecevable pour avoir été déposé hors délai. Rien ne s'oppose donc à ce que la Cour de céans prenne en considération ce second mémoire pour statuer sur le présent recours. Il n'est pas nécessaire, à cet égard, de donner suite à la requête de l'intimée tendant à ce qu'un délai supplémentaire lui soit fixé pour apporter à sa réponse les éventuelles modifications commandées par la seconde mouture du recours. Aussi bien, l'intéressée aurait eu tout loisir de le faire durant la phase d'instruction, étant donné que les deux versions du recours lui ont été communiquées en annexe à l'ordonnance l'invitant à déposer sa réponse éventuelle et qu'elle a bénéficié, de surcroît, de la possibilité de produire une duplique.
Dès lors, les considérations émises ci-après se baseront sur les motifs énoncés dans le second mémoire de recours.
2.4 La conclusion du recourant tendant à l'anonymisation des noms des parties dans le présent arrêt, hormis le fait qu'elle n'est pas dûment motivée, n'a pas de portée propre, dès lors que, conformément à l'<ref-law>, les arrêts du Tribunal fédéral sont, en principe, publiés sous une forme anonyme.
Il est plus que douteux, au demeurant, que la volonté du recourant de conserver l'anonymat soit réaliste, s'agissant d'une cause célèbre qui a déjà fait couler beaucoup d'encre et suscité, notamment en France, de nombreux commentaires publiés avec les noms des parties (cf., parmi d'autres: HORATIA MUIR WATT, Revue de l'arbitrage, 2005, p. 695 ss; THOMAS CLAY, Revue critique de droit international privé, 2006, p. 142 ss; SIMON HOTTE, Dalloz, 2005, p. 2728 ss; PHILIPPE FOUCHARD, Revue de l'arbitrage, 2002, p. 442 ss; DANIEL COHEN, Journal du droit international, 2002, p. 503 ss; PIERRE LALIVE, Bulletin de l'Association Suisse de l'Arbitrage [ASA], 2002, p. 553 ss), un auteur allant même jusqu'à réserver à l'arrêt de la Cour de cassation du 1er février 2005 une place de choix "au panthéon des grands arrêts du droit de l'arbitrage" (CLAY, op. cit., p. 142 in fine).
2.5 Lorsqu'il statue sur un recours en matière civile dirigé contre une sentence arbitrale, le Tribunal fédéral n'examine que les griefs qui ont été invoqués et motivés par le recourant (<ref-law>).
Comme il le précise dans une note figurant au pied de la page 4 de sa réplique, le recourant n'attaque pas la sentence du 10 février 2012 dans la mesure où elle a trait à l'indépendance et à l'impartialité de l'arbitre désigné par l'intimée (cf. let. B., dernier §, ci-dessus). Partant, cette question est soustraite à l'examen de la Cour de céans.
2.6 Le Tribunal fédéral statue sur la base des faits constatés dans la sentence attaquée (cf. <ref-law>). Il ne peut rectifier ou compléter d'office les constatations des arbitres, même si les faits ont été établis de manière manifestement inexacte ou en violation du droit (cf. l'<ref-law> qui exclut l'application de l'<ref-law>). L'état de fait à la base de la sentence attaquée peut toutefois être revu si l'un des griefs mentionnés à l'<ref-law> est soulevé à l'encontre dudit état de fait ou que des faits ou des moyens de preuve nouveaux sont exceptionnellement pris en considération dans le cadre de la procédure du recours en matière civile (arrêt 4A_428/2011 du 13 février 2012 consid. 1.6 et les précédents cités).
Le recourant méconnaît ces principes, qui consacre de longs passages de ses écritures à alléguer une série de faits non constatés dans la sentence entreprise, et ce sans invoquer un grief prévu par l'<ref-law> lui permettant d'exiger un complètement de l'état de fait sur lequel les arbitres ont fondé cette sentence. Ainsi en va-t-il, notamment, de son allégation, au titre des "faits pertinents nouveaux (<ref-law>)", relative à l'existence d'une ordonnance rendue le 31 juillet 2011 par son Ministre des finances pour clarifier sa position officielle vis-à-vis de l'Etat où l'intimée a son siège (recours, n. 82 à 85) ou encore de ses explications détaillées, avec schéma à l'appui, au sujet d'autres contrats, prétendument connexes à l'accord de participation, et des clauses d'arbitrage y figurant (réplique, n. 44 à 60).
Rien ne s'oppose, en revanche, à la prise en compte de l'avis de droit que le recourant a produit sous pièce n° 52, à savoir une note datée du 14 mars 2012 et émanant du professeur ... (arrêt 4A_190/2007 du 10 octobre 2007 consid. 5.1).
2.7 Il sied de relever, par ailleurs, que l'argumentation juridique contenue dans la réplique va bien au-delà de celle qui figure dans le mémoire de recours. En procédant de la sorte, le recourant oublie qu'une partie ne peut se servir d'une telle écriture ni pour invoquer des moyens, de fait ou de droit, qu'elle n'a pas présentés en temps utile, c'est-à-dire avant l'expiration du délai de recours non prolongeable, ni pour compléter, hors délai, une motivation insuffisante (arrêt 4A_14/2012 du 2 mai 2012 consid. 4).
3. 3.1 Dans un premier groupe de moyens, le recourant soutient, sur la base de l'<ref-law>, que le Tribunal arbitral a été irrégulièrement composé. Se fondant sur l'avis de droit établi le 20 septembre 2001 par le professeur ..., il fait valoir que la nomination de son arbitre n'a pas été effectuée en conformité avec l'art. 12(a) de l'accord de participation, question que les tribunaux français n'auraient pas traitée. Fort de l'opinion émise par le professeur ... dans sa note du 14 mars 2012, le recourant conteste, par ailleurs, la position de la Cour de cassation française voulant que le droit au concours du juge d'appui puisse être rattaché indirectement à l'art. 6 par. 1 de la Convention de sauvegarde des droits de l'homme et des libertés fondamentales (CEDH; RS 0.101). Il affirme en outre, en se référant à un avis de droit délivré le 8 octobre 2001 par le professeur ..., qu'on ne saurait le forcer à nommer un arbitre tant que durera la situation de conflit entre le pays où l'intimée a son siège et lui. De plus, toujours selon le recourant, une sentence rendue par un tribunal arbitral constitué sans respecter la volonté des parties ni la loi du pays où l'arbitrage se déroulera désormais, à savoir la Suisse, ne serait pas susceptible de reconnaissance et d'exécution au regard de l'art. V al. 1 let. d de la Convention de New York du 10 juin 1958 pour la reconnaissance et l'exécution des sentences arbitrales étrangères (Convention de New York; RS 0.277.12).
Dans sa réponse, l'intimée conteste, au premier chef, la recevabilité de ces moyens pour trois raisons: d'abord, parce que le Tribunal fédéral n'aurait pas la compétence de revoir la décision prise par la Cour de cassation française; ensuite, parce que le recourant commettrait un abus de droit en invoquant le grief en question alors que la mise en oeuvre des juridictions françaises serait la conséquence de la violation de son devoir de nommer un arbitre et qu'il aurait, de surcroît, reconnu expressément l'effet obligatoire des décisions françaises pour les parties; enfin, parce qu'elle s'estime en droit d'invoquer à titre préalable la reconnaissance, en Suisse, de ces décisions-là en tant qu'elles confirment la désignation de l'arbitre du recourant, les conditions d'une telle reconnaissance (art. 25 et 26 LDIP) étant à ses yeux remplies. Sur le fond, l'intimée conteste l'interprétation de la clause arbitrale, telle qu'elle est faite par le recourant. Elle soutient également que le droit français de l'arbitrage international serait seul pertinent pour déterminer si ledit arbitre a été régulièrement désigné, étant donné que le processus de désignation de celui-ci a été initié plusieurs années avant la fixation du siège de l'arbitrage à Genève. Enfin, à suivre l'intimée, la possibilité de reconnaître la sentence ne serait pas un facteur pertinent pour décider de la régularité de composition d'un tribunal arbitral.
3.2 L'<ref-law>, qui permet de sanctionner la constitution irrégulière du tribunal arbitral, couvre deux griefs: la violation des règles - conventionnelles (<ref-law>) ou légales (<ref-law>) - sur la nomination des arbitres, d'une part; le non-respect des règles touchant l'impartialité et l'indépendance des arbitres (art. 180 al. 1 let. b et c LDIP), d'autre part (PIERRE-YVES TSCHANZ, in Commentaire romand, Loi sur le droit international privé - Convention de Lugano, 2011, n° 48 ad <ref-law>). En l'espèce, seul le premier grief est soumis à l'examen du Tribunal fédéral. Les questions de droit qu'il soulève seront examinées librement (cf. <ref-ruling> consid. 3.1 et l'arrêt cité), mais dans le cadre exclusif des arguments avancés par le recourant (cf., mutatis mutandis, l'<ref-ruling> consid. 3.1; voir aussi: TSCHANZ, op. cit., n° 49 ad <ref-law>).
3.3 La cause en litige présente une double particularité qui n'est pas sans influer sur la recevabilité du grief considéré. Il s'agit, premièrement, du fait que l'arbitre du recourant a été désigné par une décision d'un tribunal français (la Cour d'appel de Paris, en date du 8 novembre 2001) que le recourant a contestée sans succès devant la plus haute juridiction civile de l'ordre judiciaire français (la Cour de cassation qui a rendu son arrêt le 1er février 2005) et, secondement, du fait que cette nomination est intervenue avant que le siège de l'arbitrage ait été fixé dans un autre pays (la Suisse, plus précisément Genève) par les arbitres désignés (décision du 19 juillet 2004 entérinant l'accord passé par les parties en décembre 2003).
3.3.1 La recevabilité du recours, on l'a vu (cf. consid. 2.2), suppose que le recourant ait un intérêt digne de protection à l'annulation de la décision attaquée. L'intérêt digne de protection consiste dans l'utilité pratique que l'admission du recours apporterait à son auteur (<ref-ruling> consid. 2.3 p. 43).
De ce point de vue, il est raisonnablement permis de se demander, au regard de la seconde circonstance mise en exergue ci-devant, si le recourant a encore un intérêt pratique, en attaquant la sentence du 10 févier 2012, à remettre indirectement en cause la décision de la Cour d'appel de Paris, avalisée par la Cour de cassation française, de lui désigner un arbitre, étant rappelé qu'il admet n'avoir aucune objection à formuler quant à l'intégrité ou la compétence de l'arbitre désigné. En effet, à supposer que le recours soit admis sur ce point et la sentence annulée, il suffirait à l'intimée de mettre en oeuvre le juge compétent du canton de Genève, siège de l'arbitrage, afin qu'il nomme la même personne en qualité d'arbitre du recourant, conformément à l'art. 179 al. 2 et 3 LDIP. Le recourant se retrouverait alors dans une situation identique à celle qui découle de la sentence attaquée. Il objecterait en vain, à cet égard, que le siège de l'arbitrage n'a pas été valablement fixé à Genève au motif qu'il l'a été par un Tribunal arbitral censé composé de manière irrégulière. Outre qu'il appartenait au premier chef aux parties de désigner le siège de l'arbitrage (<ref-law>), ce qu'elles ont fait, le Tribunal arbitral s'étant borné à entériner leur choix, pareille objection, si elle était admise, aurait pour conséquence de rendre inapplicable l'ensemble du chapitre 12 de la LDIP, faute de réalisation de la première des deux conditions cumulatives de l'<ref-law>, et, partant, entraînerait ipso jure l'irrecevabilité du présent recours dans son intégralité.
3.3.2 La première des deux particularités évoquées plus haut exclut que le Tribunal fédéral revoie le bien-fondé des décisions rendues par les juridictions françaises, jusqu'à la plus haute d'entre elles, quant à leur compétence internationale pour désigner un arbitre en lieu et place du recourant, motif pris de ce que l'intimée était exposée à un risque de déni de justice. Force est d'ailleurs de relever, en passant, que le décret n° 2011-48 du 13 janvier 2011 portant réforme de l'arbitrage a consacré, à l'art. 1505 ch. 4 du Code de procédure civile, la jurisprudence de l'arrêt de la Cour de cassation du 1er février 2005 en faisant d'un tel risque un motif suffisant à justifier la mise en oeuvre du juge d'appui français en matière d'arbitrage international.
Il est vrai que, selon la jurisprudence du Tribunal fédéral, lorsque le juge d'appui, saisi d'une demande ad hoc, nomme un arbitre, sa décision, rendue en procédure non contentieuse, ne jouit pas de l'autorité de la chose jugée, de sorte que les arbitres ont encore la faculté d'examiner de manière indépendante la compétence et la régularité de la composition du tribunal arbitral (<ref-ruling> consid. 2a; <ref-ruling> consid. 2b). La décision incidente rendue par eux sur ce point est, dès lors, sujette à recours immédiat au Tribunal fédéral (<ref-law>) pour les motifs prévus à l'art. 190 al. 2 let. a et b LDIP (cf. TSCHANZ, op. cit., n° 47 ad <ref-law>).
En l'occurrence, toutefois, la situation juridique est sans commune mesure avec celle qui vient d'être présentée et qui correspond au cas ordinaire du recours au juge d'appui suisse pour la désignation d'un arbitre dans le cadre d'un arbitrage régi par les <ref-law>. D'abord, la procédure de désignation a été conduite dans un autre pays que celui où le siège du tribunal arbitral a été fixé pendente lite et sur la base d'une autre législation que la lex fori. Ensuite, il est erroné de soutenir, comme le fait le recourant, que la nomination de son arbitre ne fut qu'une mesure de type administratif, de nature purement gracieuse, comparable aux nominations d'arbitres effectuées par la Cour d'arbitrage de la Chambre de Commerce Internationale (réplique, n. 63). Il ressort, au contraire, des explications du Tribunal arbitral et des pièces du dossier que la question de la compétence internationale des tribunaux français pour désigner un arbitre à la partie rénitente a été largement débattue et que le recourant a eu l'occasion de développer ses arguments, notamment à l'aide d'avis de droit, avant qu'une décision fût rendue en la matière par la plus haute juridiction civile de l'ordre judiciaire français, non pas prima facie, mais en pleine connaissance de tous les éléments pertinents. Enfin, il appert du chiffre 2.2.12 de la sentence attaquée que les arbitres n'ont aucunement manifesté l'intention de réexaminer les décisions prises par les juridictions françaises sur le point litigieux. Le contraire eût d'ailleurs été surprenant, car on imagine mal, du moins en pratique, qu'un tribunal arbitral s'autorise à revoir si la juridiction suprême du pays ayant entériné la désignation de l'un de ses deux membres était compétente pour ce faire au regard de sa propre législation.
Point n'est, dès lors, besoin d'examiner si, comme le soutient l'intimée, les conditions d'une reconnaissance formelle, en Suisse, des décisions rendues par la Cour d'appel de Paris et la Cour de cassation française (art. 25 et 26 LDIP) sont réalisées.
Il suit de là que le recourant n'est pas recevable à remettre en cause indirectement les décisions prises par les tribunaux français quant à leur compétence internationale pour lui désigner un arbitre contre son gré. Il l'est d'autant moins que, dans leur plaidoirie devant le Tribunal arbitral, au cours de l'audience tenue le 18 décembre 2006 à Paris, ses mandataires ont expressément renoncé à le faire, au motif que l'arrêt de la Cour de cassation revêtait un caractère final et obligatoire, et liait, en conséquence, les parties, le panel ainsi que tous les tribunaux nationaux (voir l'extrait de cette plaidoirie reproduit en original et traduit en français aux pages 24 et 25 in medio de la réplique).
Tombent également sous le coup de cette irrecevabilité les arguments, fondés sur la situation conflictuelle existant entre l'Etat où l'intimée a son siège et lui, que le recourant a déjà soumis aux juridictions françaises, en s'appuyant sur l'avis de droit du professeur ..., et qui ont été écartés par celles-ci, à tout le moins de manière implicite. De tels arguments apparaissent irrecevables, de surcroît, dans la mesure où ils reposent en partie sur un fait nouveau irrecevable (cf. consid. 2.6 ci-dessus) et parce qu'ils n'ont été développés, d'une manière conforme à l'<ref-law>, que dans la réplique (n. 98 à 105; cf. consid. 2.7 ci-dessus).
3.3.3 En définitive, la seule question à examiner dans le cadre du grief fondé sur l'<ref-law>, une fois écartées les critiques formulées de manière irrecevable à ce titre, est celle de savoir si l'art. 12 (a) de l'accord de participation s'opposait ou non à la désignation de l'arbitre du recourant par un juge d'appui, quel qu'il fût. Il n'apparaît pas, sur le vu de son arrêt du 1er février 2005, que la Cour de cassation française ait traité cette question, quand bien même elle disposait de l'avis de droit du professeur ... qui lui est consacré.
Avant d'entrer en matière et pour réfuter par anticipation une objection du recourant, il convient d'observer qu'en vertu d'une jurisprudence bien établie, applicable ici par analogie, la réponse à la question posée ne saurait dépendre de la possibilité ou non de reconnaître et d'exécuter, au regard de la Convention de New York, une éventuelle sentence au fond à venir (cf., mutatis mutandis, l'<ref-ruling> consid. 3d et l'arrêt 4A_654/2011 du 23 mai 2012 consid. 3.4 in fine).
3.4 La réponse à la question litigieuse suppose que l'on interprète la clause arbitrale figurant à l'art. 12 (a) de l'accord de participation. Pareille démarche sera effectuée à la lumière du droit suisse, conformément à l'<ref-law> et à la jurisprudence y relative (<ref-ruling> consid. 5.3.2 p. 736), dès lors que le siège de l'arbitrage a été fixé à Genève.
3.4.1 L'interprétation d'une convention d'arbitrage se fait selon les règles générales d'interprétation des contrats, sauf à dire que la jurisprudence préconise de ne pas admettre trop facilement qu'une convention d'arbitrage a été conclue, si ce point est contesté (<ref-ruling> consid. 2.2.3; <ref-ruling> consid. 2.3 p. 680 ss; <ref-ruling> consid. 2c/aa p. 58; <ref-ruling> consid. 3b p. 58). En l'espèce, toutefois, cette dernière hypothèse ne se vérifie pas puisque le recourant ne conteste pas la validité de la clause arbitrale (cf. réplique, n. 72).
Saisi d'un litige sur l'interprétation d'un contrat, le juge doit tout d'abord s'attacher à rechercher la réelle et commune intention des parties, le cas échéant empiriquement, sur la base d'indices, sans s'arrêter aux expressions et dénominations inexactes dont elles ont pu se servir (<ref-law>; <ref-ruling> consid. 3.1). Cette interprétation dite subjective relève du fait et de l'appréciation des preuves (<ref-ruling> consid. 3.1; <ref-ruling> consid. 4.1 p. 611).
S'il ne parvient pas à établir suffisamment cette volonté effective, ou s'il constate que l'une des parties contractantes n'a pas compris la volonté réelle exprimée par l'autre, le juge recherchera le sens qu'elles pouvaient et devaient donner, selon les règles de la bonne foi, à leurs manifestations de volonté réciproques (application du principe de la confiance; <ref-ruling> consid. 3.2.1). Cette interprétation objective, qui relève du droit, s'effectue non seulement d'après le texte et le contexte des déclarations, mais également sur le vu des circonstances qui les ont précédées et accompagnées, à l'exclusion des circonstances postérieures (<ref-ruling> consid. 3.2.1; <ref-ruling> consid. 3a).
3.4.2 En se référant à l'avis de droit du professeur ..., le recourant soutient, en substance, que l'on n'a pas affaire ici à une "clause pathologique par accident ou oubli", mais à une clause dont les parties ont consciemment assumé l'insuffisance dans le but de soustraire l'arbitrage à toute intervention étatique autre que celle de leurs tribunaux respectifs, étant donné la personnalité des cocontractants (un État souverain et une société nationale d'un autre État souverain), l'objectif stratégique du contrat conclu (l'utilisation du territoire du recourant pour acheminer directement le pétrole vers sa destination) et son caractère hautement secret commandé par la situation politique. C'est la raison pour laquelle la mention du siège de l'arbitrage et celle du droit applicable ont été volontairement omises dans la clause arbitrale. En d'autres termes, il s'est agi, pour les parties, d'exclure une tierce intervention, même privée, dans la désignation des coarbitres, avec la conséquence que, si l'un des États ne nommait pas son arbitre, l'arbitrage n'aurait pas lieu. Quant au choix éventuel d'un troisième arbitre, il serait effectué par une personne privée (le président de la CCI), toujours dans le même dessein.
Concrètement, le processus de résolution des litiges susceptibles d'opposer les parties devait s'articuler de la manière suivante, selon le recourant: dans une première phase, les cocontractants tenteraient de régler le différend à l'amiable. En cas d'échec de leurs pourparlers transactionnels, chacun d'eux désignerait son arbitre; à ce défaut, l'arbitrage n'aurait pas lieu, les parties ayant consciemment accepté la possibilité d'un blocage de la procédure arbitrale, sans exclure pour autant la mise en oeuvre de leurs juridictions nationales. Une fois désignés, les deux arbitres chercheraient à résoudre le litige d'un commun accord. S'ils n'y parvenaient pas, ils tenteraient de s'entendre sur le choix d'un troisième arbitre, faute de quoi le président de la CCI, à Paris, nommerait ce dernier. La sentence finale serait alors rendue par les trois arbitres. Cependant, pour assurer le plus possible leur contrôle sur ce processus de résolution des litiges et préserver leur égalité, les parties n'auraient pas accordé de voie prépondérante au troisième arbitre.
3.4.3 En l'occurrence, le Tribunal arbitral n'a pas mis en évidence une volonté concordante des parties qui confirmerait l'interprétation de l'art. 12 (a) de l'accord de participation, telle qu'elle est faite par le recourant. Il y a donc lieu de rechercher le sens de cette clause arbitrale, dont le texte a été reproduit plus haut (cf. lettre. A.a), en appliquant le principe de la confiance.
La lecture de la clause en question ne révèle aucun élément déterminant dont on pourrait inférer que l'intimée n'aurait pu attribuer, de bonne foi, aux manifestations de volonté qui y figurent que la signification que leur donne le recourant. En particulier, rien, dans le texte de cette clause, n'était propre à attirer l'attention de l'intimée sur le fait qu'en signant l'accord de participation assorti d'une telle clause, elle consentait d'emblée à ce que la procédure arbitrale mise en place pour liquider les éventuels litiges en rapport avec l'exécution de cet accord puisse être paralysée ab ovo par le simple refus de son cocontractant de désigner son arbitre. En d'autres termes, l'intimée ne devait pas objectivement déduire du texte de la clause arbitrale qu'elle pourrait être tenue, le cas échéant, nonobstant l'existence de la convention d'arbitrage, d'assigner son partenaire contractuel - le recourant - devant les juridictions étatiques du recourant. Et ce dernier ne pouvait pas non plus penser que sa cocontractante acceptait qu'il en allât ainsi du seul fait qu'elle consentait à signer l'accord de participation. Sur un plan plus général, il est d'ailleurs difficile d'admettre qu'une partie ne voie pas d'objection à conclure un contrat dont l'exécution est soumise au bon vouloir de l'autre partie contractante. S'agissant d'un accord éminemment sensible, en raison de la personnalité des partenaires contractuels et de son objet, lequel accord avait été précédé de longues négociations et mettait en jeu des intérêts financiers énormes, il n'est pas imaginable que les parties se soient accommodées consciemment de ce que l'on puisse déduire du silence de la clause arbitrale sur ce point que le refus de l'une d'elles de désigner son arbitre aurait pour conséquence, ipso jure, l'impossibilité de mettre en oeuvre ce mode de résolution de leurs différends ou de l'interrompre définitivement et qu'il forcerait la partie demanderesse à saisir les tribunaux de l'État même qui était son partenaire contractuel ou qui contrôlait la société nationale ayant qualité de partie contractante. Tout porte à croire, au contraire, que, la clause arbitrale étant rédigée de manière à préserver scrupuleusement leur égalité dans la procédure arbitrale, les cocontractants n'ont pas envisagé l'hypothèse que l'un deux refusât de nommer son arbitre.
De ce que les parties n'ont fixé ni le siège de l'arbitrage ni le droit applicable à l'art. 12 (a) de l'accord de participation, le recourant déduit leur volonté commune de ne pas rattacher l'arbitrage à un ordre juridique quelconque et d'exclure, partant, l'intervention d'autres autorités judiciaires que les juridictions de l'intimée et du recourant pour y remédier ou pour désigner un arbitre en cas de refus d'une partie de le faire (recours, n. 101; réplique, n. 43). Toutefois, cette thèse du silence qualifié repose, pour l'essentiel, sur la comparaison de l'accord litigieux avec d'autres conventions (cf. réplique, n. 44 ss) dont la prise en considération est exclue à ce stade de la procédure (cf. consid. 2.6, 2e § in fine, ci-dessus). En outre et surtout, elle se retourne contre son auteur en ce sens que le fait d'admettre la compétence supplétive des juridictions nationales des cocontractants, en tant qu'autorités judiciaires d'appui, n'est pas conciliable avec l'idée, émise par l'intéressé, selon laquelle l'arbitrage ne devait pas avoir lieu si l'une des parties refusait de nommer son arbitre.
De même, le pouvoir de décision limité que le recourant voudrait assigner au troisième arbitre éventuel ne ressort pas davantage de la teneur de la clause arbitrale. Il n'est, en effet, question, dans celle-ci, que du caractère définitif et obligatoire de "la décision du Tribunal arbitral ainsi constitué", sans autres précisions. Dans le silence du texte de ladite clause, il n'est donc pas possible d'admettre, comme le suggère apparemment le recourant dans des explications au demeurant peu claires (cf. recours, n. 98 à 100), que le troisième arbitre ne pourra pas faire pencher la balance et, semble-t-il, que la sentence devra être rendue à l'unanimité des trois arbitres.
Dans ces conditions, le Tribunal arbitral a considéré, à juste titre, que le recourant ne pouvait pas se fonder sur son interprétation erronée de la clause arbitrale pour se soustraire à son devoir, fondé sur le principe général de l'effet obligatoire des contrats (pacta sunt servanda), de désigner un arbitre et pour dénier à l'intimée le droit de saisir un juge d'appui afin de remédier à la carence de son cocontractant.
3.5 Il suit de là que le recourant invoque à tort l'<ref-law> pour soutenir que la clause arbitrale, correctement interprétée, aurait dû conduire le Tribunal arbitral à constater l'irrégularité de sa composition.
Dans la mesure où il est recevable, le recours ne peut, dès lors, qu'être rejeté sur ce point.
4. En second lieu, le recourant fait valoir que le Tribunal arbitral s'est déclaré à tort compétent (<ref-law>). Il appert toutefois de ses explications, du reste peu claires, qu'il tente en réalité, par ce biais, de soumettre à l'examen du Tribunal fédéral, sous une autre appellation, le même grief que celui qu'il lui a présenté sur le fondement de l'<ref-law>, en jouant notamment sur le sens du terme anglais jurisdiction (cf. recours, n. 118 à 133; réplique, n. 14 à 33). Autrement dit, sous le couvert de cet autre moyen, c'est toujours la désignation de son arbitre que le recourant conteste.
Il suffit d'ailleurs de lire le passage pertinent de la sentence attaquée (n. 2.2) pour constater que les deux arbitres n'y ont pas du tout abordé la question de leur compétence matérielle en rapport avec les prétentions élevées par l'intimée, mais qu'ils se sont limités à y exposer les raisons pour lesquelles ils estiment avoir été valablement désignés pour donner suite à la requête d'arbitrage fondée sur l'art. 12 (a) de l'accord de participation.
En tant qu'il aborde une question qui n'a pas encore été traitée par le Tribunal arbitral, le moyen pris de la violation de l'<ref-law>, que soulève le recourant, est, en conséquence, irrecevable. Ne le serait-il pas qu'il faudrait alors lui réserver le même sort qu'au premier grief.
5. Cela étant, il n'est pas nécessaire de rendre une décision sur la demande d'effet suspensif présentée par le recourant et admise provisoirement dans l'ordonnance présidentielle du 20 mars 2012.
6. En application des art. 66 al. 1 et 68 al. 1 et 2 LTF, le recourant devra payer les frais de la procédure fédérale et verser à son adverse partie une indemnité à titre de dépens. L'ampleur des sommes en jeu justifie la perception de l'émolument judiciaire maximal (<ref-law>).

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 à 200'000 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimée une indemnité de 250'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux mandataires des parties et au Tribunal arbitral.
Lausanne, le 10 janvier 2013
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Carruzzo