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 den Vereinigten Staaten.
Die E._ (Beklagte, Beschwerdegegnerin) ist eine Kommanditaktiengesellschaft mit Sitz in Luxemburg, die zum US-amerikanischen 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.
B.a. 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.
B.b. Mit Urteil vom 19. April 2016 hiess das Bundesgericht eine von den Klägern gegen die Beschlüsse des Handelsgerichts des Kantons Zürich vom 17. und 24. Juli 2015 erhobene Beschwerde teilweise gut, es hob die angefochtenen Beschlüsse auf und wies die Sache zu neuer Entscheidung an das Handelsgericht zurück (Verfahren 4A_474/2015).
B.c. Mit Beschluss vom 8. Juni 2016 trat das Handelsgericht des Kantons Zürich auf die Klage erneut nicht ein.
C.
Mit Beschwerde in Zivilsachen beantragen die Kläger dem Bundesgericht, es sei der Beschluss des Handelsgerichts des Kantons Zürich vom 8. Juni 2016 aufzuheben und es sei festzustellen, dass das Handelsgericht zur Beurteilung der Klage zuständig ist. Eventualiter sei der Beschluss des Handelsgerichts vom 8. Juni 2016 aufzuheben und es sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem sei der handelsgerichtliche Beschluss 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, die Beschwerdegegnerin reichte ihm eine Duplik ein.
D.
Mit Verfügung vom 5. September 2016 hiess das Bundesgericht das Sicherstellungsbegehren der Beschwerdegegnerin 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.1 mit Hinweisen).
1.1. Beim angefochtenen Beschluss vom 8. Juni 2016 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 lassen.
1.3. Nach einem Rückweisungsentscheid des Bundesgerichts sind sowohl dieses selbst als auch die kantonalen Instanzen an die rechtliche Beurteilung, mit der die Rückweisung begründet wurde, gebunden. Wegen dieser Bindung der Gerichte ist es ihnen wie auch den Parteien (abgesehen von allenfalls zulässigen Noven) verwehrt, der Beurteilung des Rechtsstreits einen anderen als den bisherigen Sachverhalt zu unterstellen oder die Sache unter rechtlichen Gesichtspunkten zu prüfen, die im Rückweisungsentscheid ausdrücklich abgelehnt oder überhaupt nicht in Erwägung gezogen worden waren (<ref-ruling> E. 2 S. 335 f. mit Hinweisen).
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 Vorinstanz habe die Parteien nach erfolgter Rückweisung nicht über den geplanten Fortgang des Verfahrens informiert. Stattdessen habe sie ohne vorgängige Anhörung der Beschwerdeführer Oberrichterin Franziska Grob durch Oberrichter Roland Schmid und Oberrichter Peter Helm durch Oberrichterin Claudia Bühler ersetzt. Durch diese Vorgehensweise sei dem verfassungsmässigen Anspruch der Beschwerdeführer auf ein gesetzmässig besetztes Gericht gemäss <ref-law> erneut nicht Genüge getan worden. Wie das Bundesgericht in den zwei im angefochtenen Entscheid aufgeführten Urteilen (<ref-ruling> E. 8.2; Urteil 4A_474/2015 vom 19. April 2016 E. 2.2.1) mit aller Deutlichkeit festgehalten habe, müsse eine Änderung des Spruchkörpers im Verlauf des Verfahrens den Parteien - gerade auch zur Wahrung des Anspruchs auf rechtliches Gehör (<ref-law>) - zwingend angekündigt werden, ansonsten es ihnen nicht möglich sei, die Sachlichkeit der Gründe für die erfolgte Besetzungsänderung substanziiert zu bestreiten. Zudem werde den Beschwerdeführern durch eine solche Vorgehensweise verunmöglicht, gegen die neu eingesetzten Oberrichter Ablehnungs- bzw. Ausstandsgründe geltend zu machen. Der angefochtene Beschluss vom 8. Juni 2016 sei daher bereits aus diesem Grund aufzuheben und die Sache zur Durchführung eines gesetzeskonformen Verfahrens an die Vorinstanz zurückzuweisen.
2.2. Die Rüge ist begründet. Das Bundesgericht hat in seinem Rückweisungsentscheid unter Hinweis auf die neuste Rechtsprechung ausgeführt, dass es bei Änderungen des einmal besetzten Spruchkörpers Aufgabe des Gerichts ist, die Parteien auf beabsichtigte Auswechslungen von mitwirkenden Richtern und deren 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 (<ref-ruling> E. 8.2; Urteil 4A_474/2015 vom 19. April 2016 E. 2.2.1).
Obwohl das Bundesgericht eine Verletzung des Anspruchs auf ein gesetzmässig besetztes Gericht (<ref-law>) im konkreten Fall darin erblickte, dass den Parteien die im Verlauf des vorinstanzlichen Verfahrens vorgenommene Änderung des Spruchkörpers nicht angekündigt worden und es den Beschwerdeführern daher nicht möglich war, die Sachlichkeit der Gründe für die Besetzungsänderung substanziiert zu bestreiten, entschied die Vorinstanz nach erfolgter Rückweisung ohne entsprechende Information der Parteien erneut über die Zuständigkeit. Dabei wurde der Spruchkörper im Vergleich zum ersten - nunmehr aufgehobenen - Zuständigkeitsentscheid erneut geändert, indem er wiederum mit denjenigen Handelsrichtern besetzt wurde, die bereits an den Entscheiden vom 12. November 2014 und 5. Dezember 2014 mitgewirkt hatten. Die Gründe dafür, weshalb am nunmehr angefochtenen Beschluss vom 8. Juni 2016 zwei andere Oberrichter als an diesen beiden Entscheidungen mitwirkten, wurde den Beschwerdeführern nicht vorgängig mitgeteilt, womit ihnen verunmöglicht wurde, die Sachlichkeit der Gründe für die erfolgte Besetzungsänderung substanziiert zu bestreiten. Entgegen der Ansicht der Beschwerdegegnerin reicht es nicht aus, dass sich die Beschwerdeführer (erstmals) im Rahmen des bundesgerichtlichen Beschwerdeverfahrens zur Änderung des Spruchkörpers äussern konnten; der Vergleich mit dem <ref-ruling> zugrunde liegenden Berufungsverfahren mit freier Prüfung von Tat- und Rechtsfragen (<ref-law>) ist nicht stichhaltig.
Mit dem geschilderten Vorgehen setzte sich die Vorinstanz über die Vorgaben im bundesgerichtlichen Rückweisungsentscheid hinweg und verletzte erneut den Anspruch auf ein gesetzmässig besetztes Gericht (<ref-law>). Dies führt ungeachtet der materiellen Begründetheit des Rechtsmittels zur Aufhebung des angefochtenen Beschlusses vom 8. Juni 2016 und zur Rückweisung der Sache an die Vorinstanz (<ref-ruling> E. 8.3 mit Hinweisen).
3.
Die Beschwerde ist teilweise gutzuheissen, der angefochtene Beschluss vom 8. Juni 2016 ist 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 wird der Beschluss des Handelsgerichts des Kantons Zürich vom 8. Juni 2016 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, 7. Februar 2017
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann