Sachverhalt: A. A.a X._ Ltd., (Beschwerdeführerin 1) ist seit Juli 1999 Alleinaktionärin der Y._ Ltd., (Beschwerdeführerin 2; gemeinsam: Beschwerdeführerinnen). Letztere baut in ihren Minen in Südafrika Flussspat (Calciumfluorid) ab. Z._ Inc. (Beschwerdegegnerin) ist ein internationaler Mischkonzern mit Sitz in den Vereinigten Staaten. Sie ist unter anderem ein bedeutender Produzent von Fluorwasserstoffsäure und benötigt dazu regelmässig grössere Mengen an Flussspat. A.b Mit Vereinbarung vom 16. Februar 2001 haben sich die Beschwerdeführerinnen verpflichtet, der Beschwerdegegnerin jährlich 85'000 WMT (wet metric tons) Flussspat zu liefern. Die Parteien vereinbarten für das Jahr 2001 einen Basispreis von USD 106.25 pro DMT (dry metric ton). Für die folgenden Jahre waren die Preise jeweils anhand einer vertraglich festgelegten Formel zu bestimmen, die auf die sogenannten FCA (Free carrier) Preise abstellte, welche die Beschwerdegegnerin anderen Lieferanten zahlte. Für den Fall, dass der anhand dieser Formel berechnete Preis unter einem definierten Mindestpreis oder über einem festgelegten Höchstpreis liegen sollte, sah die Vereinbarung eine Verpflichtung der Parteien vor, in guten Treuen einen Preis auszuhandeln, der für beide fair und angemessen ist. Die Vereinbarung wurde vorerst bis 31. Dezember 2005 abgeschlossen. Danach sollte der Vertrag jeweils um ein Jahr verlängert werden, sofern er von keiner Partei sechs Monate im Voraus gekündigt wurde. Hinsichtlich der Kündigungsmöglichkeit sieht Ziffer 3(c) unter anderem folgendes vor: "This Agreement may be terminated by either party in the following instances: (i) if either party is in material breach of the Agreement, which breach remains uncured following thirty (30) days written notice from the non-breaching party, the non-breaching party may terminate the Agreement immediately, by written notice; ..." Die Vereinbarung enthält neben einer Schiedsklausel eine Rechtswahl zugunsten des schweizerischen Rechts mit folgendem Wortlaut: "[t]his Agreement shall be construed and interpreted in accordance with the laws of Switzerland as applied between domestic parties provided, however, that the express agreements, understandings and provisions contained herein shall always prevail." A.c Am 19. Januar 2006 kündigten die Beschwerdeführerinnen die Vereinbarung vom 16. Februar 2001 fristlos mit der Begründung, die Beschwerdegegnerin habe eine wesentliche Vertragsverletzung ("material breach") begangen, indem sie sich geweigert habe, ihre Rechnungen für zwei Lieferungen vollständig zu bezahlen und den Beschwerdeführerinnen die FCA Preise offenzulegen. Die Beschwerdegegnerin bestritt die Berechtigung der Beschwerdeführerinnen zur Vertragsauflösung und machte gestützt auf verletzte Lieferpflichten Schadenersatzansprüche geltend. B. B.a Die Beschwerdegegnerin erhob am 15. Februar 2006 Schiedsklage gegen die Beschwerdeführerinnen, im Wesentlichen mit den (im Laufe des Verfahrens abgeänderten) Rechtsbegehren, es seien die Beschwerdeführerinnen zur Zahlung von USD 6'847'305.29 zuzüglich Zins von 5 % seit 19. Januar 2006 zu verpflichten. Zudem seien die Beilagen C-176 sowie C-177 streng vertraulich zu behandeln. Die Beschwerdeführerinnen machten widerklageweise Ansprüche aus erfolgten Lieferungen sowie unzutreffenden Preisberechnungen über insgesamt USD 3'830'273.35 zuzüglich Zins geltend. B.b Mit Schiedsspruch vom 3. April 2009 hiess das ICC Schiedsgericht mit Sitz in Zürich die Schiedsklage teilweise gut und verpflichtete die Beschwerdeführerinnen solidarisch zur Zahlung von Schadenersatz im Betrag vom USD 1'243'824.-- zuzüglich Zins zu 5 % seit dem 19. Januar 2006 (Dispositiv-Ziffer 1). Im Weiteren verpflichtete es die Beschwerdeführerinnen, die Beilagen C-176 und C-177 streng vertraulich zu behandeln (Dispositiv-Ziffer 2) und es wies die Widerklage ab (Dispositiv-Ziffer 3). Im Übrigen entschied es über die Verfahrenskosten (Dispositiv-Ziffern 4 und 5). Das Schiedsgericht erwog hinsichtlich der von den Beschwerdeführerinnen ausgesprochenen Kündigung, dass die Beschwerdegegnerin zwar die Vereinbarung vom 16. Februar 2001 verletzt habe, indem sie die FCA Preise den Beschwerdeführerinnen nicht offenlegte, dass diese Vertragsverletzung jedoch nicht als "material breach" im Sinne von Ziffer 3(c) der geschlossenen Vereinbarung betrachtet werden könne, weshalb die Kündigung vom 19. Januar 2006 ungerechtfertigt gewesen sei. Hinsichtlich der Widerklage der Beschwerdeführerinnen gestützt auf angeblich unzutreffende Preisberechnungen bei erfolgten Lieferungen hielt das Schiedsgericht dafür, dass nach Treu und Glauben im Geschäftsverkehr davon auszugehen sei, dass die Beschwerdeführerin 2 den von der Beschwerdegegnerin festgesetzten Preisen vorbehaltlos zugestimmt habe, indem sie diese Preise zur Grundlage ihrer unterzeichneten Rechnungen gemacht und damit auf eine rückwirkende Überprüfung der Preise formgültig verzichtet habe. Eine absichtliche Täuschung nach Art. 28 OR schloss das Schiedsgericht aus. C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführerinnen dem Bundesgericht, es seien Dispositiv-Ziffern 1 sowie 3 - 5 des ICC Schiedsspruchs vom 3. April 2009 aufzuheben, "und es sei die Angelegenheit zur Neubeurteilung an das Schiedsgericht zurückzuweisen, wobei dieses anzuweisen sei, im Sinne der Erwägungen des Bundesgerichts die Klage der Beschwerdegegnerin vollumfänglich abzuweisen und die Widerklage der Beschwerdeführerinnen vollumfänglich gutzuheissen". Eventualiter seien die genannten Dispositiv-Ziffern aufzuheben und es sei die Streitsache zur Neubeurteilung an das Schiedsgericht zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Schiedsgericht hat auf eine Vernehmlassung verzichtet. D. Mit Verfügung vom 22. Juni 2009 hiess das Bundesgericht das Sicherstellungsbegehren der Beschwerdegegnerin gut. In der Folge überwiesen die Beschwerdeführerinnen den geforderten Betrag von Fr. 35'000.-- als Sicherstellung einer allfälligen Parteientschädigung an die Gerichtskasse. Mit Verfügung vom 28. Juli 2009 wies das Bundesgericht das Gesuch der Beschwerdeführerinnen um aufschiebende Wirkung ab. Das erneute Gesuch um Erteilung der aufschiebenden Wirkung bzw. das diesbezügliche Wiedererwägungsgesuch wies es mit Verfügung vom 27. Oktober 2009 ebenfalls ab. Das Gesuch der Beschwerdeführerinnen um Ansetzung einer Frist zur Einreichung einer Replikschrift wurde mit Verfügung vom 21. Oktober 2009 abgewiesen. Am 29. Oktober 2009 reichten die Beschwerdeführerinnen dem Bundesgericht eine Replikschrift ein.