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 Art. 292 StGB 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 Art. 292 StGB 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. 