Sachverhalt:
A. A.a X._ (Beschwerdeführer) ist Inhaber des Einzelunternehmens "X._." mit Sitz in Luzern. Zweck dieser Einzelfirma ist die Übernahme von Verwaltungsratsmandaten, die Beratung und die Begleitung von Unternehmen im Bereich der Strategieentwicklung sowie bei der Strategieumsetzung.
Die Y._ AG (Beschwerdegegnerin) ist eine Versicherungsgesellschaft mit Sitz in St. Gallen. Präsident des Verwaltungsrats ist Y.A._, CEO ist Y.B._, je mit Kollektivunterschrift zu zweien beschränkt auf den Hauptsitz. Dr. Y.C._ ist als Sekretär (Nichtmitglied) des Verwaltungsrats mit Kollektivunterschrift zu zweien im Handelsregister eingetragen. Die Beschwerdegegnerin hat unter anderem eine Tochtergesellschaft in Spanien.
Am 7. März 2007 rief der Beschwerdeführer Dr. Y.C._ an und sprach mit ihm unter anderem über das Interesse der Beschwerdegegnerin am spanischen Markt. Im Einzelnen ist der Inhalt des Telefongesprächs zwischen den Parteien umstritten. Mit Schreiben vom 14. April 2007 wies der Beschwerdeführer Dr. Y.C._ auf seine im spanischen Versicherungsmarkt bestehenden Beziehungen hin und bestätigte, dass zwischen ihnen und R.A._ (R._ Partners AG, Luzern) im Hotel A._, Kloten, eine Besprechung vereinbart worden sei. Unbestrittenermassen fand die Besprechung des Beschwerdeführers mit Dr. Y.C._ und R.A._ am 17. April 2007 in Kloten statt, wobei es unter anderem darum ging, ob sich aufgrund der Kontakte von R.A._ zu einem Verwaltungsrat der Gruppe Q._ SA, Barcelona (nachfolgend: Q._), eine Möglichkeit des Kaufs einer spanischen Versicherungsgesellschaft bzw. die Kooperation mit einem Joint Venture Partner ergeben sollte. Im Übrigen ist der Inhalt der geführten Gespräche umstritten. Im Anschluss an die Sitzung zeigte sich R.A._ gegenüber Dr. Y.C._ erfreut, dass dieser die "Möglichkeit einer Übernahme evaluieren" würde, und stellte ihm weitere Unterlagen betreffend die Q._ zu.
Dr. Y.C._ teilte darauf R.A._ mit, die Beschwerdegegnerin sei "an einem vertieften Gespräch mit der von Ihnen genannten Gesellschaft weiterhin sehr interessiert und wir würden die Vermittlung entsprechender Kontakte durch Sie sehr schätzen". Am 19. Juni 2007 fand ein Treffen von R.A._ und Dr. Y.C._ sowie Q.A._, Verwaltungsratspräsident der Q._, und Q.B._, Verwaltungsratsmitglied und CEO der Q._, statt, wobei keinerlei konkrete Ergebnisse erzielt wurden. Im Übrigen ist der Inhalt des Gesprächs vom 19. Juni 2007 in Barcelona umstritten. Nachdem die Beschwerdegegnerin in der Klageantwort bestritten hatte, dass zwischen der Beschwerdegegnerin und der Q._ am Treffen vom 19. Juni 2007 weitere Gespräche vereinbart worden seien, und ausgeführt hatte, es hätten auch keine weiteren Besprechungen oder Kontakte zwischen der Beschwerdegegnerin und der Q._ stattgefunden, hielt der Beschwerdeführer lediglich fest, er bezweifle, dass zwischen dem 19. Juni 2007 und Juni 2008 nicht noch weitere Kontakte zwischen Dr. Y.C._ und der Q._ stattgefunden hätten.
A.b Mit E-Mail vom 4. Juni 2008 kontaktierte S.A._ von der S._ Spanien die Beschwerdegegnerin im Auftrag von Q.A._ und teilte ihr mit, er würde gerne ein "Lunch-Meeting" zwischen dem Verwaltungsratspräsidenten der Q._ und der Beschwerdegegnerin, Y.A._, organisieren. Zweck sei, dass sich die beiden Präsidenten, Q.A._ und Y.A._, persönlich kennen lernen würden, und dass Q.A._ Y.A._ einige strategische Gedanken präsentieren möchte, um zu sehen, ob es Sinn mache, diese Ideen allenfalls weiter zu verfolgen. In der Folge organisierte S.A._ auf den 11. Juli 2008 ein Treffen zwischen ihm, Y.A._, Y.B._ und Q.A._ am Hauptsitz der Beschwerdegegnerin in St. Gallen. Im Schreiben vom 14. Juli 2008 teilte Q.A._ Y.A._ im Wesentlichen mit, dass verschiedene Gemeinsamkeiten bezüglich Strategie und Geschäftsgebaren der beiden Gesellschaften bestünden. Im Übrigen erwähnte er aber in keiner Weise, dass konkrete Resultate in Bezug auf eine Kooperation der beiden Gesellschaften, die direkte Konkurrenten im spanischen Markt sind, erzielt worden seien. Für den November 2008 vereinbarten Y.A._ und Y.B._ ein Treffen mit Q.A._ am Hauptsitz der Q._ in Barcelona. Gemäss den Ausführungen der Beschwerdegegnerin äusserte Q.A._ beiläufig unter anderem den Wunsch, bei einem Freiwerden eines Aktienpaketes der Beschwerdegegnerin oder einer anderen günstigen Gelegenheit allenfalls Aktien der Beschwerdegegnerin unter der Meldeschwelle von 3 % zu erwerben.
Mit Schreiben vom 14. Januar 2009 teilte der Beschwerdeführer der Beschwerdegegnerin unter Bezugnahme auf die "Gespräche im April 2007 betreffend den Versicherungsmarkt Spanien" mit, er habe R.A._ gebeten, "die Möglichkeiten in Spanien nochmals abzuklären".
Gemäss den Ausführungen der Beschwerdegegnerin teilte ein Blockaktionär ihr im Frühjahr 2009 mit, dass er ein Aktienpaket von knapp 4 % veräussern möchte. Da dieser Aktionär eine schnelle Veräusserung des Pakets gewünscht habe und der Kurs aufgrund des widrigen Kapitalmarktumfeldes sehr tief gewesen sei, habe Y.B._ Q.A._ kontaktiert und ihn auf das freiwerdende Aktienpaket aufmerksam gemacht. Unbestrittenermassen erwarb die Q._ in der Folge von diesem Blockaktionär im Rahmen einer ausserbörslichen Transaktion ein Aktienpaket von 2 % zu einem marktüblichen, tiefen aber nicht veröffentlichten Preis.
Nachdem der Beschwerdeführer über R.A._ von dessen spanischen Informanten vom Erwerb von 2 % des Aktienkapitals der Beschwerdegegnerin durch die Q._ erfahren hatte, machte er gegenüber der Beschwerdegegnerin "unter Bezugnahme auf unsere Gespräche von 2007" einen Provisionsanspruch geltend, worauf die Beschwerdegegnerin diese Forderung zurückwies.
B. Am 8. Juli 2010 reichte der Beschwerdeführer beim Handelsgericht des Kantons St. Gallen Klage ein mit den Rechtsbegehren, die Beschwerdegegnerin sei "unter Androhung der Überweisung an den Strafrichter zur Bestrafung nach <ref-law> zu verpflichten, dem Kläger sämtliche Belege, Urkunden, Verträge etc.
a) bezüglich des Verkaufs von Namenaktien der Y._ AG durch die Beklagte an die Gruppe Q._ SA, Barcelona, Spanien, sowie
b) betreffend die beklagtische Vermittlung von im Besitz Dritter befindlicher Namenaktien der Beklagten an die Gruppe Q._ SA herauszugeben.
[2.] Die Beklagte sei unter Vorbehalt der Nachklage zu verpflichten, dem Kläger die Provision von 3 % auf dem gesamten Kaufpreis, wie er sich aus den von der Beklagten gemäss Ziffer 1 hiervor herauszugebenden Belegen ergibt, im Betrag von mindestens Fr. 1'000'000.-- zu bezahlen", nebst Zins zu 5 % ab verschiedenen Daten. Zur Begründung seiner Klage gab er an, er habe einen Anspruch aus einem Mäklervertrag mit der Beschwerdegegnerin. Es sei aufgrund seiner Mäklertätigkeit zu einer Zusammenarbeit zwischen der Q._ und der Beschwerdegegnerin gekommen und infolgedessen zu einer Beteiligung von 2 % Ersterer an der Letzteren. Damit sei der durch den Mäklervertrag angestrebte Erfolg eingetreten und der Mäklerlohn geschuldet.
Die Beschwerdegegnerin beantragte Abweisung der Klage. Sie bestritt, dem Beschwerdeführer je einen Auftrag erteilt zu haben. Der Beschwerdeführer habe ihr von sich aus einen Kontakt mit der Q._ vermittelt. Die Beschwerdegegnerin wäre einzig an einem Kauf von Unternehmensteilen der Q._ interessiert gewesen. Diese habe aber offensichtlich kein Interesse an einem Verkauf gehabt, weshalb keine weiteren Gespräche in dieser Sache mehr stattgefunden hätten. Ein erneuter Kontakt zwischen der Beschwerdegegnerin und der Q._, der rund ein Jahr später stattgefunden habe, sei nicht auf das Tätigwerden des Beschwerdeführers zurückzuführen und sei zudem nicht über einen freundschaftlichen Austausch hinausgegangen. Die Q._ habe, nachdem sie von der Beschwerdegegnerin auf ein frei werdendes Aktienpaket aufmerksam gemacht worden sei, im Frühjahr 2009 Aktien der Beschwerdegegnerin im Umfang von 2 % gekauft, wobei jedoch dieser Aktienkauf ohne jeglichen Kausalzusammenhang zur untauglichen Aktion des Beschwerdeführers ein Jahr zuvor zu Stande gekommen sei.
Mit Entscheid vom 29. Februar 2012 wies das Handelsgericht die Klage ab.
C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, den Entscheid des Handelsgerichts vom 29. Februar 2012 aufzuheben. Die Beschwerdegegnerin sei "unter Androhung der Überweisung an den Strafrichter zur Bestrafung nach <ref-law> zu verpflichten, dem Kläger sämtliche Belege, Urkunden, Verträge etc.
a) bezüglich des Verkaufs von Namenaktien der Y._ AG durch die Beklagte an die Gruppe Q._ SA, Barcelona, Spanien, sowie
b) betreffend die beklagtische Vermittlung von im Besitz Dritter befindlicher Namenaktien der Beklagten an die Gruppe Q._ SA herauszugeben.
[3.] Die Beklagte sei unter Vorbehalt der Nachklage zu verpflichten, dem Kläger die Provision von 3 % auf dem gesamten Kaufpreis, wie er sich aus den von der Beklagten gemäss Ziffer 2 hiervor herauszugebenden Belegen ergibt, im Betrag von mindestens Fr. 1'000'000.-- zu bezahlen", nebst Zins zu 5 % ab verschiedenen Daten.
Eventualiter sei das Verfahren zur Ergänzung des Sachverhalts und Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin beantragt, den angefochtenen Entscheid zu bestätigen und die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Vorinstanz verzichtete auf eine Vernehmlassung.
Mit Präsidialverfügung vom 30. Mai 2012 wurde das Gesuch um Erteilung der aufschiebenden Wirkung abgewiesen.

Erwägungen:
1. Der angefochtene Entscheid des Handelsgerichts ist ein Endentscheid, gegen den die Beschwerde zulässig ist (<ref-law>). Das Handelsgericht hat als einzige kantonale Instanz im Sinne von <ref-law> entschieden. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde - unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 und 106 Abs. 2 BGG) - grundsätzlich einzutreten.
2. 2.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht kann das Bundesgericht nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.3.1; <ref-ruling> E. 2.1; <ref-ruling> E. 3.2 S. 444).
Unerlässlich ist im Hinblick auf <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Der Beschwerdeführer soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die er im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit seiner Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2.1).
2.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (vgl. <ref-ruling> E. 1.2; <ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3, 393 E. 7.1, 462 E. 2.4). Soweit der Beschwerdeführer den Sachverhalt ergänzen will, hat er zudem mit Aktenhinweisen darzulegen, dass er entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (Urteile 4A_214/2008 vom 9. Juli 2008 E. 1.2, nicht publ. in: <ref-ruling>; 4A_275/2011 vom 20. Oktober 2011 E. 2). Überdies ist in der Beschwerde darzutun, inwiefern die Behebung des gerügten Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2). Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (BGE <ref-ruling> E. 1.4.3).
2.3 Zu betonen ist, dass das Bundesgericht auch im Rahmen von Beschwerden gegen Urteile der Handelsgerichte keine Appellationsinstanz ist, die sämtliche Rechtsfragen und den Sachverhalt umfassend überprüft. Nicht eingetreten werden kann daher auf Vorbringen des Beschwerdeführers, mit denen er den vorinstanzlichen Erwägungen in bloss appellatorischer Weise seine eigene Auffassung entgegensetzt oder unsubstanziierte Sachverhaltsrügen erhebt.
3. Die Vorinstanz wies die Klage im Wesentlichen mit der Begründung ab, der Beschwerdeführer habe nicht nachgewiesen, dass ein tatsächlicher oder normativer Konsens zwischen den Parteien im Hinblick auf den Abschluss eines Mäklervertrags vorgelegen habe. Zudem wäre auch der Kausalzusammenhang zwischen der angeblichen Mäklertätigkeit und dem Vertragsschluss nicht erstellt. Selbst wenn man den Abschluss eines Mäklervertrags und einen Kausalzusammenhang annehmen würde, hätte der Beschwerdeführer keinen Provisionsanspruch, da der Aktienkauf nicht Inhalt des behaupteten Mäklervertrags gewesen wäre. Der Beschwerdeführer ficht - richtigerweise (vgl. <ref-ruling> E. 6.3) - alle drei Begründungen an, die je für sich allein die Klageabweisung zu stützen vermögen.
4. 4.1 Durch den Mäklervertrag erhält der Mäkler den Auftrag, gegen eine Vergütung, Gelegenheit zum Abschluss eines Vertrages nachzuweisen oder den Abschluss eines Vertrages zu vermitteln (<ref-law>). Der Mäklerlohn ist verdient, sobald der Vertrag infolge des Nachweises oder der Vermittlung des Mäklers zustande gekommen ist (<ref-law>). Zur Begründung des Mäklerlohnes hat der Mäkler zu beweisen, dass der im Mäklervertrag bezeichnete Hauptvertrag infolge seiner Bemühungen abgeschlossen worden ist (<ref-ruling> E. 5.1.2 S. 275; <ref-ruling> E. 3a S. 483). Ohne anderslautende Vereinbarung muss zwischen der Mäklertätigkeit und dem Vertragsabschluss ein Kausalzusammenhang bestehen, wobei ein psychologischer Zusammenhang zwischen den Bemühungen des Mäklers und dem Entschluss des Dritten ausreicht (<ref-ruling> E. 5 S. 549; Urteil 4A_337/2011 vom 15. November 2011 E. 2.1; je mit weiteren Hinweisen).
Der Mäklervertrag kann durch konkludentes Verhalten abgeschlossen werden, wobei verlangt wird, dass das Verhalten des Mäklers hinreichend klar sein muss, damit das Schweigen des Auftraggebers als Zustimmung interpretiert werden kann (BGE 72 II 84 E. 1b S. 87; Urteil 4C.328/2006 vom 16. Oktober 2007 E. 3.1 mit Hinweisen).
4.2 Im Konsens- wie im Auslegungsstreit gilt es, in erster Linie den übereinstimmenden wirklichen Parteiwillen festzustellen (<ref-law>). Erst wenn eine tatsächliche Willensübereinstimmung unbewiesen bleibt, sind zur Ermittlung des mutmasslichen Parteiwillens die Erklärungen der Parteien aufgrund des Vertrauensprinzips so auszulegen, wie sie nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen verstanden werden durften und mussten. Für die Auslegung nach dem Vertrauensprinzip ist der Zeitpunkt des Vertragsabschlusses massgeblich. Nachträgliches Parteiverhalten ist dafür nicht von Bedeutung; es kann höchstens - im Rahmen der Beweiswürdigung - auf einen tatsächlichen Willen der Parteien schliessen lassen. Während das Bundesgericht die objektivierte Vertragsauslegung als Rechtsfrage prüfen kann, beruht die subjektive Vertragsauslegung auf Beweiswürdigung, die vorbehältlich der Ausnahmen von Art. 97 und 105 BGG der bundesgerichtlichen Überprüfung entzogen ist (<ref-ruling> E. 3.2; <ref-ruling> E. 3.1 mit Hinweisen). Dasselbe gilt für die Feststellungen des kantonalen Richters über die äusseren Umstände sowie das Wissen und Wollen der Beteiligten im Rahmen der Auslegung nach dem Vertrauensprinzip (<ref-ruling> E. 2.2.1 mit Hinweisen).
5. Die Vorinstanz gelangte in Würdigung der Parteivorbringen und der Akten, namentlich der im Anschluss an das Treffen vom 17. April 2007 erfolgten Korrespondenz zum Schluss, gemäss der Sachdarstellung des Beschwerdeführers fehle es an einem natürlichen Konsens. Der Beschwerdeführer habe den Nachweis, dass ein solcher, wie behauptet, anlässlich des Telefongesprächs vom 7. März 2007 vorgelegen habe, weder aufgrund von schriftlichen Unterlagen erbracht, noch könnten den Akten hinreichende Indizien für einen mündlichen Vertragsschluss entnommen werden. Überdies habe er den Inhalt des behaupteten Mäklervertrags nicht schlüssig dargelegt.
Der Beschwerdeführer erhebt gegen die vorinstanzliche Verneinung eines natürlichen Konsenses ein Bündel von Rügen: Die Vorinstanz habe unrichtige Feststellungen getroffen sowie <ref-law>, <ref-law>, <ref-law> und <ref-law> verletzt, weil sie seine Behauptungen bezüglich Vertragsschluss als nicht genügend substanziiert beurteilt und prozesskonform beantragte Beweise nicht abgenommen habe. Sodann habe sie die Verhandlungsmaxime und gleichzeitig das Willkürverbot verletzt, indem sie das Zustandekommen eines Mäklervertrags verneint habe, obwohl dies von der Beschwerdegegnerin anerkannt worden sei.
Soweit auf diese Rügen mit Blick auf das Erfordernis einer hinlänglichen Begründung (vgl. Erwägung 2) eingetreten werden kann, ist dazu Folgendes zu bemerken:
5.1 Zunächst kann von einer willkürlichen Handhabung der Verhandlungsmaxime nach Art. 56 Abs. 1 des Zivilprozessgesetzes des Kantons St. Gallen vom 20. Dezember 1990 keine Rede sein, da die Beschwerdegegnerin den Abschluss eines Mäklervertrags mit dem Beschwerdeführer stets bestritten und gerade nicht anerkannt hat. Der Beschwerdeführer will eine Anerkennung in der Ausführung in der Klageantwort erblicken, wonach die Beschwerdegegnerin bereit gewesen wäre, dem Beschwerdeführer eine Entschädigung zu bezahlen, wenn aufgrund seiner Hinweise der Kauf einer spanischen Versicherungsgesellschaft möglich gewesen wäre. Laut Vorinstanz bestritt die Beschwerdegegnerin aber gleichzeitig, den Beschwerdeführer je beauftragt oder von seinen Bemühungen gewusst zu haben, oder, dass sie mit solchen auch nur hätte rechnen müssen. Die Beschwerdegegnerin hat somit im kantonalen Verfahren bestritten, dass eine - theoretisch denkbare - Beauftragung des Beschwerdeführers entweder ausdrücklich oder konkludent erfolgt war. Die Rüge einer (willkürlichen) Missachtung der Verhandlungsmaxime geht daher fehl.
Ebenso ins Leere trifft der in diesem Zusammenhang erhobene Vorwurf des Beschwerdeführers, die Vorinstanz argumentiere in Widerspruch zur (angeblichen) Anerkennung eines Vertragsschlusses und ihre tatsächlichen Feststellungen verletzten daher <ref-law>. Da in der zitierten Ausführung gerade keine Anerkennung eines Vertragsschlusses erblickt werden kann, entfällt auch ein diesbezüglich widersprüchliches und willkürliches Argumentieren.
5.2 Zu den objektiv wesentlichen Elementen des Mäklervertrags gehören die Entgeltlichkeit und die Erfolgsbedingtheit aufgrund der Tätigkeit des Mäklers - sei es zum Nachweis oder zur Vermittlung eines Vertrags (<ref-ruling> E. 5.1.2 S. 275; <ref-ruling> E. 3a S. 482). Entsprechend durfte die Vorinstanz verlangen, dass der Beschwerdeführer hinreichend substanziiert vorbringe, welches die vereinbarten Tätigkeiten hätten sein sollen, für die er - bei eingetretenem Erfolg - vereinbarungsgemäss ein Honorar hätte fordern können. Dass er diesen bundesrechtskonformen Substanziierungsanforderungen nachgekommen wäre, vermag der Beschwerdeführer auch mit den Hinweisen auf gewisse seiner Ausführungen in der Klage und der Replik nicht aufzuzeigen, geht doch daraus nicht mit hinreichender Bestimmtheit hervor, welche "Aktivitäten" bzw. Tätigkeiten der Beschwerdeführer als Mäkler hätte entfalten sollen, um den Honoraranspruch zu verdienen. Jedenfalls ist es nicht bundesrechtswidrig, wenn die Vorinstanz darin nicht erkennen konnte, welches die vertraglich geschuldeten Bemühungen des Beschwerdeführers hätten sein sollen und bei welcher Tätigkeit genau ihm die Beschwerdegegnerin eine Provision hätte zahlen müssen. Dass sie darüber hinaus Angaben zur Höhe und den Berechnungsgrundlagen der Provision vermisste, was der Beschwerdeführer als Verletzung von <ref-law> rügt, ist nicht entscheidwesentlich. Relevant ist, dass der Beschwerdeführer mit seinen nur vagen Ausführungen die objektiv wesentlichen Elemente des behaupteten Mäklervertrags nicht hinlänglich bestimmt substanziierte, namentlich nicht präzis darlegte, was seine provisionsbegründende Tätigkeit hätte sein sollen.
Fehlte es aber bereits an rechtsgenüglich substanziierten Behauptungen zum Inhalt des angeblich abgeschlossenen Vertrags, konnte und musste die Vorinstanz keine Beweise zum Vorliegen eines natürlichen Konsenses betreffend den Vertragsinhalt abnehmen. In einleuchtender Weise führte sie aus, dass dem Gericht im Rahmen von Parteieinvernahmen keine neuen Behauptungen hätten vorgelegt werden dürfen, weshalb darauf verzichtet werden könne.
5.3 Der Beschwerdeführer beanstandet, dass die Vorinstanz auf die von ihm beantragte Einvernahme seiner Person und von Dr. Y.C._ als Partei und von Zeugen, insbesondere von R.A._, verzichtete. Sie habe damit <ref-law> und <ref-law> verletzt.
Der Vorwurf ist unbegründet. Es genügt nicht, Beweise zu offerieren. Erforderlich ist, dass genau angegeben wird, für welche Behauptungen die beantragten Partei- und Zeugeneinvernahmen Beweis erbringen sollen. Nun vermisste die Vorinstanz aber genau solche konkreten Behauptungen, begründete sie den Verzicht auf die Partei- und Zeugeneinvernahmen doch damit, dass der Beschwerdeführer die Relevanz für die Frage des Abschlusses eines Mäklervertrags nicht dargetan habe.
Der Beschwerdeführer widerspricht dem und führt aus, er und Dr. Y.C._ seien Teilnehmer des Telefongesprächs vom 7. März 2007 als auch der nachfolgenden Besprechung vom 17. April 2007 gewesen. Nur schon aus diesem Umstand ergebe sich die Relevanz von ihren Aussagen für den Vertragsschluss und -inhalt. Auch R.A._ sei Teilnehmer der Sitzung vom 17. April 2007 gewesen, woraus die Relevanz seiner Zeugenaussagen in Bezug auf den Vertragsschluss folge. Sodann seien Z._ und Y.A._ ebenfalls in die "Verhandlungen der Parteien und R.A._ sowie der Q._ involviert" gewesen, weshalb sie ein rechtserhebliches, mittelbares Zeugnis zum Thema "Vertragsschluss und -inhalt" ablegen könnten.
Mit diesen Ausführungen vermag der Beschwerdeführer nicht zu kontern, dass seine Klage bereits an der Behauptungslast scheiterte. Der blosse Umstand, dass die besagten Personen eine Rolle in den Gesprächen spielten, ersetzt noch keine Behauptungen, für die mit den Aussagen Beweis erbracht werden soll. Es ist nicht Aufgabe des Gerichts, im Rahmen der Befragungen nach solchen zu forschen. Aus demselben Grund verletzte die Vorinstanz <ref-law> auch nicht deshalb, weil sie "das zur Edition offerierte Verwaltungsratsprotokoll der auf die Besprechung vom 17. April 2007 folgenden Verwaltungsratssitzung der Beschwerdegegnerin" nicht abnahm. Wenn der Beschwerdeführer meint, aus den daraus ersichtlichen Umständen würde sich die Relevanz für die Frage, ob ein Vertrag aufgrund eines tatsächlichen Konsenses zustande gekommen sei, ergeben, so verkennt er einmal mehr, dass Beweise zu konkreten Behauptungen zu offerieren sind und nicht ihrerseits bezwecken dürfen, nach relevanten Tatsachen erst zu suchen. Mangels prozessual gehöriger Behauptungen war die Vorinstanz zur Abnahme der beantragten Beweismittel nicht verpflichtet. Eine Verletzung von <ref-law> liegt nicht vor.
5.4 Nach dem Gesagten gehen sämtliche Rügen gegen die Verneinung eines natürlichen Konsenses fehl. Es bleibt somit dabei, dass der Beschwerdeführer den Abschluss eines Mäklervertrags zwischen den Parteien nicht darzutun vermochte mangels substanziierter Behauptung eines tatsächlich übereinstimmenden Willens bezüglich des notwendigen Inhalts eines Mäklervertrags.
6. Die Vorinstanz vermochte auch in Anwendung des Vertrauensprinzips keinen Abschluss eines Mäklervertrags zu erkennen.
6.1 Der Beschwerdeführer kritisiert zutreffend, dass die Vorinstanz sich im Zusammenhang mit der Prüfung eines normativen Konsenses des Ausdrucks bediente, der Vertragsabschluss sei "nicht nachgewiesen". Die Kritik bleibt aber ohne Auswirkung auf den Entscheid. Denn die Vorinstanz verkannte trotz der kritisierten Ausdrucksweise nicht, dass die Frage, ob ein Vertrag aufgrund eines normativen Konsenses zustande kam, rechtlicher Natur ist. So prüfte sie, ob das Verhalten von Dr. Y.C._ von der Beschwerdegegnerin dazu führte, dass der Beschwerdeführer in guten Treuen davon habe ausgehen können und dürfen, mit der Beschwerdegegnerin in einer vertraglichen Beziehung zu stehen. Ein entsprechendes Verhalten von Dr. Y.C._ konnte die Vorinstanz indessen nicht ausmachen. Ebenso wenig war ein Verhalten des Beschwerdeführers als (angeblicher) Mäkler von hinreichender Bestimmtheit erstellt, das seitens der Beschwerdegegnerin wissentlich geduldet oder stillschweigend genehmigt worden wäre. Es fehlte somit bereits am Nachweis der tatsächlichen Umstände, aufgrund derer ein normativer Konsens allenfalls hätte angenommen werden können. Auch wenn es sich bei der Anwendung des Vertrauensprinzips um eine Rechtsfrage handelt, waren die tatsächlichen Grundlagen, welche die Annahme eines normativen Konsenses allenfalls erlaubt hätten, vom Beschwerdeführer zu erstellen (vgl. Erwägung 4.2 in fine). Davon ging die Vorinstanz zutreffend aus.
6.2 Der Beschwerdeführer ist weiter der Ansicht, die Vorinstanz hätte die beantragten Partei- und Zeugeneinvernahmen zu den einen normativen Konsens begründenden "äusseren Umständen" sowie "zum Wissen und Wollen der Beteiligten" durchführen müssen. Indem sie stattdessen vom entsprechenden fehlenden Nachweis ausgegangen sei, habe sie <ref-law> und <ref-law> verletzt.
Dem kann nicht gefolgt werden. Auch an dieser Stelle ist vielmehr festzuhalten, dass die genannten Personen nur zu konkreten Behauptungen betreffend einen Vertragsschluss am 7. März 2007, eventualiter am 17. April 2007, hätten befragt werden können. Dass der Beschwerdeführer solche Behauptungen aufgestellt hätte, zeigt er nicht auf. Er vermag daher auch mit seiner Kritik gegen die Verneinung eines normativen Konsenses nicht durchzudringen.
7. Zusammenfassend ist es nicht zu beanstanden, wenn die Vorinstanz weder einen natürlichen noch einen normativen Konsens zum Abschluss eines Mäklervertrags zwischen den Parteien erkannte. Da sie die Klage somit bereits aus diesem Grund rechtskonform abgewiesen hat, erübrigt es sich zu prüfen, ob auch ihre Eventualbegründungen der Kritik des Beschwerdeführers standgehalten hätten.
Da der Beschwerdeführer demnach die eingeklagte Provisionsforderung nicht auf einen mit der Beschwerdegegnerin abgeschlossenen Mäklervertrag stützen kann und die Forderungsklage abzuweisen ist, erweist sich sein (materiellrechtliches) Auskunfts- bzw. Editionsbegehren von vornherein als unbegründet, und die Vorinstanz hat auch dieses zu Recht abgewiesen, ohne dass dazu weitere Ausführungen erforderlich wären.
8. Der Vollständigkeit halber ist schliesslich zu erwähnen, dass auch auf die Kritik gegen die Ablehnung des prozessualen Editionsbegehrens durch die Vorinstanz nicht eingegangen zu werden braucht. Nach den Hinweisen des Beschwerdeführers in der Beschwerde hätten die zur Edition beantragten Unterlagen im Zusammenhang mit den Eventualbegründungen der Vorinstanz Relevanz gehabt. Einzig das Protokoll der auf die Besprechung vom 17. April 2007 folgenden Verwaltungsratssitzung der Beschwerdegegnerin, dessen Edition er beantragte, erwähnte der Beschwerdeführer im Rahmen seiner Ausführungen gegen die Hauptbegründung der Vorinstanz. Dies jedoch ohne Erfolg, wie vorne ausgeführt wurde (Erwägung 5.3).
9. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 12'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 14'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 31. Juli 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Kölz