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.