Sachverhalt:
A. Die A. & Co._ (Beschwerdeführerin) mit Sitz in W._ ist als Kommanditaktiengesellschaft konstituiert und bezweckt den "Betrieb einer Bank, insbesondere einer Vermögensverwaltungs-, Börsen- und Effektenbank". Präsident des Verwaltungsrates der Beschwerdeführerin und unbeschränkt haftender Gesellschafter ist A._.
Die B._ AG (vormals "C. S._ AG"; Beschwerdegegnerin) mit Sitz in X._ bezweckt die "Produktion und Vertrieb von sowie Handel mit Fernsehprogrammen, anderen Medienprodukten sowie damit zusammenhängender Software, Vermarktung von Werberechten (...), Organisation und Marketing von sportlichen und kulturellen Anlässen sowie Beratung in den Bereichen Sport- und Anlasssponsoring (...)". A._ amtete bis zum 7. Mai 2003 als Verwaltungsrat der Beschwerdegegnerin mit Kollektivunterschrift zu zweien.
Mit Beschluss des Amtsgerichts München vom 14. Juni 2002 wurde über die Muttergesellschaft der Beschwerdegegnerin, die C. M._ GmbH & Co. KGaA mit Sitz in Y._, das Insolvenzverfahren eingeleitet, wobei Eigenverwaltung des Vermögens angeordnet wurde. Mit Kaufvertrag vom 31. Oktober 2002 wurden die Aktien der Beschwerdegegnerin an die E._ AG mit Sitz in Z._ veräussert. In der Folge machte die Beschwerdeführerin geltend, der Vertragsabschluss vom 31. Oktober 2002 beruhe auf einem Mäklervertrag zwischen der Beschwerdeführerin als Mäklerin und der Beschwerdegegnerin als Auftraggeberin bzw. auf entsprechenden Bemühungen seitens der Beschwerdeführerin für die Beschwerdegegnerin. Am 20. Dezember 2002 machte die Beschwerdeführerin gegenüber der Beschwerdegegnerin als Vermittlungsprovision den Betrag von EUR 9'468'800.-- geltend. Gestützt auf eine Abtretungserklärung vom 3. Dezember 2004 erhob die Beschwerdeführerin zudem gegenüber der Beschwerdegegnerin persönliche Ansprüche A._. Die Beschwerdegegnerin bestritt jegliche Schuldpflicht gegenüber der Beschwerdeführerin.
B. Am 4. September 2003 reichte die Beschwerdeführerin beim Kantonsgericht Zug Klage ein und beantragte, die Beschwerdegegnerin sei zu verpflichten, ihr den Betrag von EUR 9'468'800.-- evtl. CHF 13'919'136.-- zu bezahlen. Weiter sei von ihrer Bereitschaft Vormerk zu nehmen, an die Beschwerdegegnerin gerichtete Rechnungen der F._, sowie von G._, bis zum Maximalbetrag von EUR 1.5 Mio. (inkl. MWSt) zu eigenen Lasten zu begleichen oder, soweit von der Beschwerdegegnerin bereits schon bezahlt, die Rechnungsbeträge an ihre Klageforderung anrechnen zu lassen. Die Beschwerdegegnerin beantragte Abweisung der Klage.
Mit Vorentscheid vom 24. Februar 2005 verwarf das Kantonsgericht die von der Beschwerdegegnerin erhobene Einrede der mangelnden Passivlegitimation. Mit Urteil vom 11. Dezember 2006 wies es die Klage ab.
Gegen dieses Urteil reichte die Beschwerdeführerin Berufung beim Obergericht des Kantons Zug ein. Sie beantragte, das angefochtene Urteil aufzuheben, und erneuerte im Wesentlichen ihr vor Kantonsgericht gestelltes Klagebegehren, ergänzt mit einem Eventualantrag auf Rückweisung der Sache an jenes zur Fortsetzung des Beweisverfahrens und zur Neubeurteilung. Mit Urteil vom 2. Dezember 2008 wies das Obergericht die Berufung ab, soweit es darauf eintrat und bestätigte das Urteil des Kantonsgerichts.
C. Die Beschwerdeführerin beantragt mit Beschwerde in Zivilsachen, das Urteil des Obergerichts vom 2. Dezember 2008 aufzuheben und die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. Eventuell sei die Klage vom 4. September 2003 gutzuheissen.
Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne, und das angefochtene Urteil zu bestätigen. Das Obergericht schliesst auf Abweisung der Beschwerde unter Verzicht auf Gegenbemerkungen.

Erwägungen:
1. 1.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss 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. 2.2; <ref-ruling> E. 3.2). Macht der Beschwerdeführer eine Verletzung des Willkürverbots von <ref-law> geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich; er hat vielmehr im Einzelnen aufzuzeigen, inwiefern dieser offensichtlich unhaltbar ist (<ref-ruling> E. 3 S. 352). Auf rein appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.1; <ref-ruling> E. 3.1 S. 399).
1.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substantiiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3).
1.3 Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür nur auf, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgrundsatz zuwiderläuft. Willkür liegt zudem nur vor, wenn nicht bloss die Begründung eines Entscheids, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 1.3; <ref-ruling> E. 4.1; <ref-ruling> E. 3.1).
Zu beachten ist, dass dem Sachgericht im Bereich der Beweiswürdigung ein erheblicher Ermessensspielraum zusteht. Das Bundesgericht greift auf Beschwerde hin nur ein, wenn das Sachgericht sein Ermessen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (vgl. <ref-ruling> E. 2.1; <ref-ruling> E. 2.1; <ref-ruling> E. 4b S. 40; <ref-ruling> E. 1b S. 30).
2. 2.1 Die Vorinstanz gelangte in Würdigung der Aussagen von A._ an der erstinstanzlichen Verhandlung, insbesondere zur Telefonkonferenz vom 23. Mai 2002, zum Beweisergebnis, es sei erstellt, dass zwischen den Parteien kein Mäklervertrag zufolge ausdrücklicher Willensäusserungen zustande gekommen sei. Vor dem Hintergrund der Aussagen von A._ und der Behauptungen der Beschwerdeführerin sei nicht ersichtlich, inwiefern die von der Beschwerdeführerin verlangte Beweisabnahme an diesem Ergebnis etwas zu ändern vermöchte. Den Abschluss eines Mäklervertrags konnte die Vorinstanz auch nicht aus dem mit Schreiben der Beschwerdeführerin vom 12. Juli 2002 der Beschwerdegegnerin zugestellten Entwurf eines Mandatsvertrags und der daraufhin von I._ von der Beschwerdegegnerin ergangenen E-Mail vom 5. August 2002 ableiten. Ebenso stützte sie die Würdigung der Erstinstanz, dass auch an der Verwaltungsratssitzung vom 4. September 2002 kein Mäklervertrag zustande gekommen sei.
2.2 Nach Auffassung der Beschwerdeführerin verletzt die Beweiswürdigung der Vorinstanz das Willkürverbot (<ref-law>) und die darauf gestützte Ablehnung, weitere Beweise abzunehmen, den Anspruch auf rechtliches Gehör (<ref-law>).
2.2.1 Was das vorinstanzliche Beweisergebnis als solches angeht, zeigt die Beschwerdeführerin nicht klar und substantiiert auf, inwiefern dieses willkürlich sein soll. Statt dessen unterbreitet sie dem Bundesgericht in appellatorischer Weise ihre eigene Sicht der Dinge und legt in weitschweifigen Ausführungen unter freier Ergänzung des vorinstanzlich festgestellten Sachverhalts dar, wie die Aussagen von A._ ihrer Ansicht nach zu würdigen wären. Sie scheint dabei zu verkennen, dass das Bundesgericht keine letzte Appellationsinstanz ist, die von den Parteien mit vollkommenen Rechtsmitteln angerufen werden könnte. Sie müsste in Auseinandersetzung mit den Erwägungen der Vorinstanz aufzeigen, dass dieselben geradezu willkürlich im Sinne der Rechtsprechung (vgl. Erwägung 1.3 vorne) wären, was sie jedoch nicht tut. Mit ihren appellatorischen Vorbringen, die den vorstehend (Erwägung 1) dargestellten Begründungsanforderungen nicht genügen, ist die Beschwerdeführerin nicht zu hören.
2.2.2 Ebenso wenig begründet sie hinlänglich, inwiefern die Vorinstanz in diesem Zusammenhang den Anspruch auf rechtliches Gehör verletzt haben soll.
Der aus dem Anspruch auf rechtliches Gehör fliessende Anspruch auf Abnahme und Würdigung rechtzeitig und formrichtig angebotener Beweismittel (vgl. <ref-ruling> E. 2 S. 242; <ref-ruling> E. 4a mit Hinweisen) schliesst eine vorweggenommene Beweiswürdigung nicht aus, verbietet dem Gericht also nicht, einem beantragten Beweismittel die Erheblichkeit oder Tauglichkeit abzusprechen oder auf die Abnahme von Beweisen zu verzichten, wenn das Gericht aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und willkürfrei davon ausgehen darf, diese würde durch weitere Beweiserhebungen nicht geändert (<ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 3 S. 157; <ref-ruling> E. 2.1 S. 429).
Das Bundesgericht greift in eine antizipierte Beweiswürdigung nur ein, wenn sie willkürlich und damit offensichtlich unhaltbar ist, namentlich wenn sie eine prozessuale Vorschrift oder einen unumstrittenen Grundsatz des Beweisrechts krass verletzt oder sonst wie in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.1; <ref-ruling> E. 2.1). Inwiefern dies zutreffen soll, ist in der Beschwerde klar und detailliert aufzuzeigen, was entsprechend substantiierte Willkürrügen voraussetzt. Erweist sich die antizipierte Beweiswürdigung als willkürfrei, liegt in ihr keinerlei Verletzung des Anspruchs auf rechtliches Gehör (BGE <ref-ruling> E. 3 S. 157).
Es gelingt der Beschwerdeführerin von vornherein nicht, die antizipierte Beweiswürdigung der Vorinstanz als willkürlich auszuweisen, indem sie einfach behauptet, aus den Aussagen von A._ ergebe sich bei zutreffender Auslegung, dass er der Meinung gewesen sei, die Beschwerdegegnerin sei die Honorarschuldnerin.
Sie macht sodann geltend, jedenfalls entfalle die Beschwerdegegnerin aufgrund der Aussagen von A._ nicht zwingend als Honorarschuldnerin. Bei diesem Ergebnis hätte die Vorinstanz die weiter beantragten Beweise abnehmen müssen. Im gleichen Sinn argumentiert sie betreffend die E-Mail vom 5. August 2002 und die Verwaltungsratssitzung vom 4. September 2002. Nach ihrer Auffassung steht weder anhand der E-Mail vom 5. August 2002 noch aufgrund der Verwaltungsratssitzung vom 4. September 2002 fest, dass kein Mäklervertrag aufgrund ausdrücklicher Willensäusserungen zustande gekommen sei. Da diese Frage offen geblieben sei, hätten die von der Beschwerdeführerin angebotenen Beweise abgenommen werden müssen. Auch mit diesen Ausführungen bringt die Beschwerdeführerin wiederum lediglich ihre eigene Meinung zum Ausdruck, weist die Argumentation der Vorinstanz aber nicht einmal ansatzweise als willkürlich aus.
Die Vorinstanz erblickte in den Aussagen von A._ nicht nur keinen Beweis dafür, dass zwischen den Parteien ein Mäklervertrag zustande gekommen sei, sondern umgekehrt den Beleg dafür, dass kein Mäklervertrag kraft ausdrücklicher Willenserklärung abgeschlossen worden sei. Nachdem dieser Schluss mangels hinlänglich begründeter Willkürrüge Bestand hat, durfte die Vorinstanz ohne Verletzung von <ref-law> in antizipierter Beweiswürdigung auf die Abnahme weiterer Beweise verzichten. Dass sie in Willkür verfallen wäre, indem sie annahm, weitere Beweiserhebungen vermöchten an der gewonnenen Überzeugung nichts zu ändern, zeigt die Beschwerdeführerin in keiner Art auf.
3. Die Vorinstanz hielt mit der Erstinstanz auch einen konkludenten oder stillschweigenden Vertragsabschluss für nicht nachgewiesen.
3.1 Sie führte aus, wenn der Mäkler die ausdrückliche Auftragserteilung nicht beweisen könne, so könne er sich darauf berufen, er habe dem Auftraggeber seine Vermittlerdienste angeboten und dieser habe sie angenommen. Der Abschluss des Mäklervertrages sei dabei durch stillschweigende Annahme der Vermittlerdienste eines Mäklers nach allgemeinen auftragsrechtlichen Grundsätzen möglich. Die den Mandatskonsens bewirkende stillschweigende Annahme sei die wissentliche Duldung oder die stillschweigende Genehmigung der Mäklertätigkeit. Nötig sei jedenfalls, dass dem Auftraggeber nach den Umständen klar sein müsse, dass der Mäkler für ihn tätig werden wolle und daher im Falle erfolgreicher Tätigkeit von ihm Vergütung erwarte. Damit das Fehlen eines Widerspruchs seitens des Auftraggebers als Wille zum Abschluss eines Mäklervertrags interpretiert werden könne, sei ein Verhalten des Mäklers von genügender Bestimmtheit erforderlich. Seine Tätigkeit müsse entweder durch ihre Dauer oder kraft ihrer Bedeutung geeignet sein, eine Dienstofferte darzustellen.
Im konkreten Fall unterstützte sie die Beurteilung der Erstinstanz, die ausführte, für die Zeit bis zur Unterbreitung des schriftlichen Mandatsentwurfs seitens der Beschwerdeführerin mit Schreiben vom 12. Juli 2002 fehle es am Nachweis eines hinreichend klaren Angebots der Beschwerdeführerin. Selbst wenn ein solches erfolgt wäre, wäre es mit der E-Mail von I._ vom 5. August 2002 endgültig und unmissverständlich abgelehnt worden. Zudem könne der an A._ gerichtete Auftrag, zur Finanzierung des geplanten "Management-supported Buyout" einen geeigneten Finanzinvestor zu finden, durchaus als Sonderaufgabe eines Verwaltungsratsmitgliedes der Beschwerdegegnerin ausgestaltet gewesen sein, da sowohl in der Gesprächsnotiz zur Besprechung, die einen Tag nach der Telefonkonferenz vom 23. Mai 2002 stattgefunden habe, als auch im Protokoll der Verwaltungsratssitzung vom 12. Juni 2002 jeweils von einem Auftrag an A._ persönlich und nicht an die Beschwerdeführerin die Rede sei. Hinzu komme, dass die Beschwerdegegnerin gar nicht als Partei des abzuschliessenden Kaufvertrages in Frage gekommen sei und es bei dessen tatsächlichem Abschluss denn auch nicht gewesen sei. Die nach dem abschlägigen Bescheid der Beschwerdegegnerin ausgeführte Tätigkeit der Beschwerdeführerin sei offensichtlich nicht zum Nutzen der Beschwerdegegnerin, sondern zu jenem des Managements der Beschwerdegegnerin erfolgt, welches die Loslösung der Beschwerdegegnerin von der insolventen C._Gruppe angestrebt habe. Später habe die Beschwerdeführerin auch die Interessen der vom Management der Beschwerdegegnerin als Käufer bevorzugten Investorengruppe um H._ gewahrt. Unter diesen Umständen habe die Beschwerdegegnerin gerade nicht davon ausgehen müssen, dass die erwähnte Tätigkeit für sie erfolgt sei und von ihr im Falle erfolgreichen Wirkens eine Vergütung erwartet werden würde. Die Beschwerdeführerin habe somit den Nachweis eines hinreichend klaren Angebotes, für die Beschwerdegegnerin als Mäklerin tätig werden zu wollen, nicht erbracht.
3.2 Die Beschwerdeführerin unterzieht diese Erwägungen der Vorinstanz wiederum bloss einer appellatorischen Kritik, indem sie ihnen ihre eigene Darstellung der Geschehnisse und die eigene Interpretation der Abläufe und Urkunden gegenüber stellt, teilweise unter Wiedergabe ihrer Ausführungen in den kantonalen Rechtsschriften. Eine rechtsgenüglich begründete Willkürrüge ist darin nicht zu erkennen. Dies namentlich auch, soweit die Beschwerdeführerin geltend macht, die Vorinstanz sei in Willkür verfallen und habe den Gehörsanspruch verletzt, indem sie das Ergebnis ihrer Beweiswürdigung - wonach die Beschwerdeführerin den Nachweis eines hinreichend klaren Angebotes, für die Beschwerdegegnerin als Mäklerin tätig werden zu wollen, nicht erbracht habe - als derart eindeutig betrachtete, dass sie aufgrund der gewonnenen Überzeugung auf weitere Beweiserhebungen verzichten durfte. Darzutun wäre, dass die Ansicht der Vorinstanz, ihre Überzeugung würde durch weitere Beweiserhebungen nicht geändert, offensichtlich unhaltbar sei. Solches zeigt die Beschwerdeführerin aber in keiner Weise auf.
4. 4.1 Schliesslich rügt die Beschwerdeführerin eine Verletzung der aus dem Anspruch auf rechtliches Gehör fliessenden Begründungspflicht. Die Vorinstanz habe sich mit den Aussagen von A._ nicht im Einzelnen auseinandergesetzt, sondern sich in einer Pauschalwürdigung ergangen. Sie beschränke sich auf die Auffassung, dass sich infolge der gewonnen Überzeugung weitere Beweiserhebungen erübrigten, ohne ein Wort darüber zu verlieren, inwiefern die Tatsachenbehauptungen und Beweise, auf die nicht eingetreten werde, nichts am vom Gericht erkannten Ergebnis zu ändern vermöchten.
4.2 Der Anspruch auf rechtliches Gehör verlangt unter anderem, dass das Gericht die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, sorgfältig und ernsthaft prüft und in der Entscheidfindung berücksichtigt. Daraus folgt die grundsätzliche Pflicht des Gerichts, den Entscheid zu begründen. Die Begründung eines Entscheids muss so abgefasst sein, dass der Betroffene ihn gegebenenfalls sachgerecht anfechten kann. Die Begründung muss kurz die wesentlichen Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die sich sein Entscheid stützt. Nicht erforderlich ist hingegen, dass sich der Entscheid mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt (<ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 3.3 S. 445; <ref-ruling> E. 3.2 S. 236, je mit Hinweisen).
Diesen Anforderungen vermag der angefochtene Entscheid ohne weiteres zu genügen, da sich aus der Begründung ergibt, dass sich die Vorinstanz mit der zentralen Frage, ob ein Vertragsschluss nachgewiesen sei, eingehend auseinandergesetzt hat. Dabei reicht es aus, wenn sie darlegte, aus welchen Gründen sie zum Schluss gelangte, dass aufgrund der Aussagen von A._ erstellt sei, dass kein ausdrücklicher Vertragsschluss zustande gekommen sei und weitere Beweiserhebungen an dieser gewonnenen Überzeugung nichts zu ändern vermöchten. Sie musste nicht im Einzelnen erwähnen, welche Beweise die Beschwerdeführerin noch beantragt hatte, und ausführen, weshalb ihre Erhebung nichts an der gerichtlichen Erkenntnis zu ändern vermöchte.
Die Rüge der Verletzung des Gehörsanspruchs erweist sich demnach als unbegründet.
5. Zusammenfassend sind die Beweiswürdigung und entsprechende Schlussfolgerung der Vorinstanz, dass es der Beschwerdeführerin nicht gelungen sei, den - ausdrücklichen oder konkludenten - Abschluss eines Mäklervertrages zwischen den Parteien zu beweisen, aufgrund der erhobenen Rügen nicht zu beanstanden und es liegt keine Gehörsverletzung vor. Die Beschwerde ist demnach abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens wird die Beschwerdeführerin 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. 40'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 50'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zug, Zivilrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 4. Mai 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Widmer