Sachverhalt: A. A.a. A._ (Kläger 1, Beschwerdeführer 1) ist ein in der Erdölindustrie tätiger Experte und Geschäftsmann mit Wohnsitz in U._, Vereinigte Staaten. Er hält die in der Erdölindustrie tätigen Gesellschaften B._, C._ und D._ (Klägerinnen 2-4, Beschwerdeführerinnen 2-4), je mit Sitz in U._, Vereinigte Staaten. Die E._ (Beklagte, Beschwerdegegnerin) ist eine Kommanditaktiengesellschaft mit Sitz in Luxemburg, die zum Mineralölkonzern F._ gehört. Die Beklagte verfügt über eine Zweigniederlassung in Zürich. A.b. Der Kläger 1 hat nach eigenen Angaben als Experte im Bereich der Exploration und Förderung von Öl- und Gasvorkommen Ende der 1980er-Jahre eines der weltweit grössten Vorkommen von Erdöl, Gas und Schwefel entdeckt und dazu Informationen unter anderem betreffend Lage, tektonische Umgebung, Qualität und Förderbarkeit erstellt. Nachdem er in der Folge von der Regierung beauftragt worden sei, zwecks Bewirtschaftung der Vorkommen ein internationales Konsortium zu bilden, habe er die von ihm erarbeiteten Informationen den Ölgesellschaften G._ und H._ zur Verfügung gestellt. Schliesslich sei ein Konsortium gebildet worden, das aus G._, einer anderen europäischen Ölgesellschaft, I._ und J._ bestanden habe. Im Rahmen dieses Konsortiums habe dem Kläger 1 ein Fünftel des Nettoerlöses zugestanden. Die Bewirtschaftung der Vorkommen durch das Konsortium sei jedoch nie in Schwung gekommen. Der Grund dafür sei gewesen, dass G._, H._, K._, F._ sowie weitere grosse Ölfirmen selbst ein Konsortium zur Bewirtschaftung der genannten Vorkommen gebildet hätten. Dieses habe ohne Einwilligung des Klägers 1 die von ihm erarbeiteten Informationen verwendet, durch Bestechung hochrangiger Beamter Lizenzen für die Bewirtschaftung der vom Kläger 1 entdeckten Vorkommen erworben und die Vorkommen in der Folge bewirtschaftet, ohne den Kläger 1 zu entschädigen. Aufgrund rechtswidriger Verwendung von Arbeitserzeugnissen des Klägers 1 durch die Muttergesellschaft der Beklagten, die F._, verlangten die Kläger in der Folge die Herausgabe des im Rahmen der Ausbeutung der fraglichen Rohstoffvorkommen erzielten Gewinns, welcher der Beklagten als Tochtergesellschaft zuteilgeworden sei. B. Mit Eingabe vom 30. Juli 2014 klagten die Kläger beim Handelsgericht des Kantons Zürich im Wesentlichen auf Gewinnherausgabe in einem noch unbezifferten Betrag sowie auf Auskunft und Rechnungslegung. Mit Verfügung vom 6. August 2014 wurde den Klägern Frist angesetzt, um für die Gerichtskosten einstweilen einen Vorschuss von Fr. 31'000.-- zu leisten. Dieser wurde fristgerecht eingezahlt. Nachdem die Beklagte beantragt hatte, es sei ein höherer Gerichtskostenvorschuss einzufordern und es sei ihre Parteientschädigung sicherzustellen, wurde den Klägern mit Beschluss vom 12. November 2014 Frist angesetzt, um einstweilen einen zusätzlichen Vorschuss für die Gerichtskosten von Fr. 500'000.-- und eine Sicherheit für die Parteientschädigung im Betrag von Fr. 800'000.-- zu leisten. Mit Eingabe vom 1. Dezember 2014 stellten die Kläger einen Antrag auf Beschränkung des Verfahrens auf das auf Auskunft und Rechnungslegung gerichtete Rechtsbegehren sowie sinngemäss auf Wiedererwägung des Beschlusses vom 12. November 2014. Mit Beschluss vom 5. Dezember 2014 wurden diese Anträge abgewiesen. In der Folge gingen auch der zusätzliche Kostenvorschuss und die Sicherheit für die Parteientschädigung bei der Gerichtskasse ein. Mit Eingabe vom 3. März 2015 reichte die Beklagte eine "uneinlässliche" Klageantwort ein und beantragte in erster Linie, es sei auf die Klage mangels Zuständigkeit nicht einzutreten. Mit Eingabe vom 12. Juni 2015 nahmen die Kläger zum Hauptantrag auf Nichteintreten und zu den Eventualanträgen der Beklagten Stellung. Die Beklagte äusserte sich dazu unaufgefordert mit Eingabe vom 26. Juni 2015. Mit Beschluss vom 17. Juli 2015 trat das Handelsgericht des Kantons Zürich mangels örtlicher Zuständigkeit nicht auf die Klage ein. Mit Beschluss vom 24. Juli 2015 berichtigte es den Entscheid vom 17. Juli 2015 hinsichtlich der Parteientschädigung dahingehend, dass diese Entschädigung der Beklagten erst nach Rechtskraft des Beschlusses von der Obergerichtskasse aus der von den Klägern geleisteten Sicherheit ausbezahlt werde. C. Mit Beschwerde in Zivilsachen beantragen die Kläger dem Bundesgericht, es seien die Beschlüsse des Handelsgerichts des Kantons Zürich vom 17. Juli 2015 und vom 24. Juli 2015 aufzuheben und es sei festzustellen, dass das Handelsgericht des Kantons Zürich zur Beurteilung der Klage vom 30. Juli 2014 zuständig ist. Eventualiter seien die Beschlüsse vom 17. Juli 2015 und vom 24. Juli 2015 aufzuheben und es sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem sei der Beschluss des Handelsgerichts vom 12. November 2014 aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin beantragt, es sei auf die Beschwerde nicht einzutreten; eventualiter sei diese abzuweisen. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. Die Beschwerdeführer reichten dem Bundesgericht eine Replik ein; die Beschwerdegegnerin verzichtete auf eine Stellungnahme dazu. D. Mit Verfügung vom 9. November 2015 hiess das Bundesgericht das Sicherstellungsbegehren der Beschwerdegegnerin teilweise gut und es forderte die Beschwerdeführer auf, als Sicherstellung einer allfälligen Parteientschädigung an die Beschwerdegegnerin Fr. 100'000.-- zu hinterlegen. Der Betrag ging in der Folge bei der Bundesgerichtskasse ein.