Sachverhalt: A. A.a. Die X._ SE (Beschwerdeführerin 1) ist eine Europäische Aktiengesellschaft (Societas Europaea) mit Sitz in Wien. Die Y._ GmbH (Beschwerdeführerin 2) ist eine Gesellschaft mit beschränkter Haftung österreichischen Rechts mit Sitz in I._ (Österreich). Die Z._ B.V. (Beschwerdegegnerin) ist eine geschlossene Kapitalgesellschaft niederländischen Rechts mit Sitz in Amsterdam. A.b. Die Beschwerdegegnerin und die Q._ GmbH als Verkäuferinnen schlossen am 30. Juli 2008 mit den Beschwerdeführerinnen als Käuferinnen einen Aktienkaufvertrag ab (Share Purchase and Acquisition Agreement [SPA]). Gegenstand des Vertrags waren sämtliche Aktien der R._ AG, einer österreichischen Tochtergesellschaft der Beschwerdegegnerin. Auf den Vertrag ist gemäss Ziffer 14.2 SPA österreichisches Recht anwendbar. Gemäss Ziffer 8.1 SPA stand der Vertrag u.a. unter der aufschiebenden Bedingung, dass die kartellrechtliche Freigabe durch die österreichischen Wettbewerbsbehörden und weitere Instanzen erteilt werde. In Ziffer 8.5 SPA haben die Parteien vereinbart, dass sie ihre "best endeavours" einsetzen würden, um diese Bedingung zu erfüllen. Gemäss Ziffer 8.7 SPA durfte jede Partei vom Vertrag zurücktreten, falls der Unternehmenszusammenschluss nicht innert elf Monaten seit Unterzeichnung des SPA genehmigt würde, sofern die zurücktretende Partei sich selbst an die Bestimmungen des SPA gehalten hatte ("[...] provided that the Party intending to rescind this Agreement has complied with all terms and obligations of the SPA"). A.c. Da die kartellrechtliche Freigabe in der Folge nicht innert vertraglich vereinbarter Frist erwirkt werden konnte, erklärten die Beschwerdeführerinnen am 1. Juli 2009 den Rücktritt vom Vertrag. Per 16. September 2009 trat auch die Beschwerdegegnerin vom Vertrag zurück. In der Folge stellte sich die Beschwerdegegnerin auf den Standpunkt, der Rücktritt der Beschwerdeführerinnen sei ungültig, da diese ihrer vertraglichen Pflicht zur Förderung der kartellrechtlichen Freigabe ("best endeavours") gemäss Ziffer 8.5 SPA nicht genügt hätten. B. Gestützt auf die Schiedsklausel in Ziff. 14.3 SPA leitete die Beschwerdegegnerin am 19. Oktober 2009 ein Schiedsverfahren bei der Internationalen Handelskammer (ICC) ein. Mit ihrer Schiedsklage verlangte sie zuletzt die Zahlung von EUR 140 Mio. zuzüglich Zins und rund EUR 5 Mio. Verzugszins mit Zinseszins. Die Beschwerdeführerinnen verlangten die Abweisung der Klage und machten widerklageweise Zahlung von EUR 800'000.-- nebst Zins für frustrierte Aufwendungen aufgrund von Vertragsverletzungen der Beschwerdegegnerin geltend. Mit Schiedsentscheid vom 29. Mai 2012 stellte das Dreierschiedsgericht mit Sitz in Zürich fest, dass der Rücktritt der Beschwerdeführerinnen zu Unrecht erfolgt und damit wirkungslos ist (Ziff. 1), wohingegen der Rücktritt der Beschwerdegegnerin rechtmässig und wirksam ist (Ziff. 2). Weiter verurteilte das Schiedsgericht die Beschwerdeführerinnen zur Zahlung von Schadenersatz im Umfang von EUR 30 Mio. nebst laufenden und aufgelaufenen Zinsen an die Beschwerdegegnerin (Ziff. 3) und wies die Widerklage der Beschwerdeführerinnen ab (Ziff. 5). C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführerinnen dem Bundesgericht, es sei der Schiedsentscheid vom 29. Mai 2012 aufzuheben und es sei die Sache zur teilweisen Wiederholung des Beweisverfahrens (Wiederholung der Zeugenbefragungen) sowie zur Ergänzung des Beweisverfahrens an die Vorinstanz zurückzuweisen. Weiter sei der Beschwerde die aufschiebende Wirkung zu erteilen. Die Beschwerdegegnerin beantragt in ihrer Vernehmlassung die Abweisung der Beschwerde, soweit Eintreten. Die Vorinstanz beantragt Abweisung. Die Beschwerdeführerinnen reichten in der Folge Replik, die Beschwerdegegnerin und die Vorinstanz Duplik ein. Mit Schreiben vom 24. Juli 2012 erklärten die Beschwerdeführerinnen, das Gesuch um Gewährung der aufschiebenden Wirkung zurückzuziehen. D. Mit Präsidialverfügung vom 25. Juli 2012 wurde das Gesuch um Gewährung der aufschiebenden Wirkung infolge Rückzugs abgeschrieben.