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.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 2 S. 59; <ref-ruling> E. 1 S. 133; je mit Hinweisen).
1.1. Beim angefochtenen Beschluss vom 17. bzw. 24. Juli 2015 handelt es sich um einen Endentscheid im Sinne von <ref-law>. Für Beschwerden in Zivilsachen gegen Urteile kantonaler Handelsgerichte besteht kein Streitwerterfordernis (<ref-law> i.V.m. <ref-law> [SR 272]; <ref-ruling> E. 1.2 S. 69).
Demgegenüber handelt es sich beim Beschluss vom 12. November 2014 um einen Zwischenentscheid. Als solcher ist er durch Beschwerde gegen den Endentscheid anfechtbar, soweit er sich auf dessen Inhalt auswirkt (<ref-law>). Unabhängig davon, ob diese Voraussetzung vorliegend erfüllt ist, beanstanden die Beschwerdeführer lediglich, die Vorinstanz sei von einem zu hohen Streitwert ausgegangen, ohne daraus jedoch konkrete Anträge hinsichtlich Vorschuss und Sicherstellung bzw. Festsetzung der Prozesskosten abzuleiten; der blosse Rückweisungsantrag reicht nicht aus (<ref-ruling> E. 1.2; <ref-ruling> E. 1.3 S. 383; <ref-ruling> E. 3.1). Auf die entsprechenden Ausführungen ist nicht einzugehen.
1.2. Im Übrigen ist auf die Beschwerde - unter Vorbehalt einer hinreichenden Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) - einzutreten. Entgegen der Ansicht der Beschwerdegegnerin trifft nicht zu, dass sich der Beschwerde keine rechtsgenügenden Rügen entnehmen liessen.
2.
Die Beschwerdeführer werfen der Vorinstanz vor, den Anspruch auf ein gesetzmässig besetztes Gericht (<ref-law>) verletzt zu haben.
2.1. Sie bringen vor, die vorliegend relevanten Beschlüsse der Vorinstanz seien jeweils in völlig unterschiedlicher Zusammensetzung ergangen. So seien an den Beschlüssen vom 12. November und 5. Dezember 2014 jeweils Oberrichter Heim (gemeint: Helm), Oberrichterin Grob, die Handelsrichter Haessig, Heim und Furrer sowie die leitende Gerichtsschreiberin Egloff beteiligt gewesen. Der Beschluss vom 17. Juli 2015 sei daraufhin in der Besetzung Oberrichter Helm, Oberrichterin Bühler, Handelsrichter Weber, Mathé und Müller sowie Gerichtsschreiberin Ohnjec ergangen. Schliesslich sei der Beschluss vom 24. Juli 2015 in der Besetzung Oberrichter Helm (recte: Daetwyler), Oberrichterin Bühler, Handelsrichter Heim, Müller und Graber sowie Gerichtsschreiberin Scheider gefasst worden.
Für die gänzlich unterschiedliche Zusammensetzung des Spruchkörpers bei den Beschlüssen vom 17. und 24. Juli 2015 im Vergleich zu denjenigen vom 12. November und 5. Dezember 2014 sei kein Grund ersichtlich. Die erfolgte Änderung in der Zusammensetzung des Spruchkörpers sei unzulässig, könne es doch nicht im Belieben eines Gerichts liegen, fortlaufend Beschlüsse in jeweils völlig unterschiedlicher personeller Zusammensetzung zu treffen. Vielmehr hätten die Beschwerdeführer einen Anspruch auf einen konstant zusammengesetzten Spruchkörper. Dieser sei zur Instruktion und zum Entscheid in der Sache zuständig, nicht aber das gesamte Handelsgericht in jeweils beliebig unterschiedlicher Zusammensetzung. Durch die gänzlich unterschiedlichen Zusammensetzungen des Spruchkörpers ohne jeden sachlichen Grund sei ihr Anspruch auf eine rechtmässige Zusammensetzung des Gerichts bzw. auf ein in personeller Hinsicht zuständiges bzw. ordentlich besetztes Gericht gemäss <ref-law> verletzt worden.
2.2.
2.2.1. Nach der neueren Rechtsprechung kann der Anspruch auf ein durch Gesetz geschaffenes Gericht verletzt sein (<ref-law>), wenn die Zusammensetzung des Spruchkörpers im Verlauf des Verfahrens ohne hinreichende sachliche Gründe geändert wird. Jede Besetzung, die sich nicht mit sachlichen Gründen rechtfertigen lässt, verletzt die Garantie des verfassungsmässigen Richters (<ref-ruling> E. 2.2.1 S. 342 mit Hinweisen). Eine Veränderung der Besetzung ist einzelfallbezogen zulässig, beispielsweise wenn ein Mitglied des Gerichts aus Altersgründen ausscheidet oder wegen einer länger dauernden Krankheit oder Mutterschaftsurlaub das Amt nicht ausüben kann oder wenn eine Neukonstituierung des Gerichts die Auswechslung erfordert (Urteile 4A_271/2015 vom 29. September 2015 E. 6.2; 5A_429/2011 vom 9. August 2011 E. 3.2; 4A_473/2014 vom 11. Dezember 2014 E. 4.2; 8C_58/2014 vom 24. September 2014 E. 2.3; 1B_277/2013 vom 15. April 2014 E. 2; 4A_263/2012 vom 22. Oktober 2012 E. 2.1.2; 6P.102/2005 vom 26. Juni 2006 E. 2.2).
Das Bundesgericht hat in diesem Zusammenhang in einem neuen Entscheid darauf hingewiesen, dass es bei Änderungen des einmal besetzten Spruchkörpers Aufgabe des Gerichts ist, die Parteien auf beabsichtigte Auswechslungen von mitwirkenden Richtern und die Gründe dafür hinzuweisen. Erst wenn der Partei die Gründe für die Besetzungsänderung bekannt gegeben worden sind, liegt es an ihr, deren Sachlichkeit substanziiert zu bestreiten (Urteil 4A_271/2015 vom 29. September 2015 E. 8.2, zur Publikation vorgesehen).
2.2.2. Wie sich aus den vorinstanzlichen Akten ergibt, ergingen die beiden Beschlüsse vom 12. November und 5. Dezember 2014 in derselben Besetzung. In der Folge wechselte jedoch der Spruchkörper und der Nichteintretensbeschluss vom 17. Juli 2015 wurde - mit Ausnahme des vorsitzenden Oberrichters Helm - in gänzlich geänderter Zusammensetzung gefasst. Die Änderung des Spruchkörpers im Verlauf des vorinstanzlichen Verfahrens wurde den Parteien nicht angekündigt. Auch im bundesgerichtlichen Verfahren äusserte sich die Vorinstanz nicht zu den Gründen für den Wechsel. Den Beschwerdeführern war es damit nicht möglich, die Sachlichkeit der Gründe für die erfolgte Besetzungsänderung substanziiert zu bestreiten. Entgegen der Ansicht der Beschwerdegegnerin, die diesen Umstand wie auch die aufgeführten Grundsätze des gebotenen Vorgehens nach neuster Rechtsprechung verkennt, ist der in der Beschwerde erhobene Vorwurf der Verletzung des Anspruchs auf ein gesetzmässig besetztes Gericht demnach begründet.
Dies führt aufgrund der formellen Natur des Anspruchs nach <ref-law> ungeachtet der materiellen Begründetheit des Rechtsmittels zur Aufhebung der angefochtenen Beschlüsse vom 17. und 24. Juli 2015 und zur Rückweisung der Sache an die Vorinstanz (Urteil 4A_271/2015 vom 29. September 2015 E. 8.3 mit Hinweisen, zur Publikation vorgesehen).
3.
Die Beschwerde ist teilweise gutzuheissen, die angefochtenen Beschlüsse vom 17. und 24. Juli 2015 sind aufzuheben und die Sache ist zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Bei diesem Verfahrensausgang wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG). Den Beschwerdeführern ist die von ihnen an die Bundesgerichtskasse bezahlte Sicherheitsleistung von Fr. 100'000.-- zurückzuerstatten.

Demnach erkennt das Bundesgericht:
1.
In teilweiser Gutheissung der Beschwerde werden die Beschlüsse des Handelsgerichts des Kantons Zürich vom 17. und 24. Juli 2015 aufgehoben und die Sache wird zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Die Gerichtskosten von Fr. 10'000.-- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt Fr. 12'000.-- zu entschädigen.
4.
Die von den Beschwerdeführern an die Bundesgerichtskasse bezahlte Sicherheitsleistung von Fr. 100'000.-- wird diesen zurückerstattet.
5.
Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 19. April 2016
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann