Sachverhalt: A. A.a A._ (Kläger 1, Beschwerdeführer 1) ist seit Jahren als Medienunternehmer tätig. Er betreibt durch die Z._ AG (Klägerin 2, Beschwerdeführerin 2) einen Radiosender. Der Kläger 1 ist zu 97.5 % an der Klägerin 2 (beide gemeinsam: Kläger, Beschwerdeführer) beteiligt. B._ (Beklagter, Widerkläger, Beschwerdegegner) ist Verleger und Medienunternehmer. Er ist Verwaltungsratspräsident eines Schweizer Medienunternehmens. A.b B._ äusserte sich im Rahmen eines Interviews vom 16. Februar 2011, das im Internet veröffentlicht wurde, über A._ und das von diesem aufgebaute Unternehmen. Die Kläger halten diese Äusserung für unlauter im Sinne des Bundesgesetzes gegen den unlauteren Wettbewerb (UWG). A.c A._ veröffentlichte in der Folge einen Artikel, in dem er sich seinerseits über B._ und dessen Unternehmen äusserte. Der Beklagte und Widerkläger hält dies seinerseits für widerrechtlich. B. Am 15. Februar 2012 klagten A._ und die Z._ AG beim Handelsgericht des Kantons Zürich gegen B._ und verlangten im Wesentlichen die Feststellung, dass bestimmte Äusserungen des Beklagten unlauter sind und eine widerrechtliche Verletzung ihrer wettbewerbsrechtlichen Stellung darstellen. Im Weiteren beantragten sie, es sei dem Beklagten unter Strafandrohung zu verbieten, bestimmte Äusserungen zu tätigen, das Dispositiv des Urteils sei auf Kosten des Beklagten zu veröffentlichen, und er sei zur Zahlung einer Genugtuung von Fr. 10'000.-- samt Zins zu verurteilen. Der Beklagte bestritt die Zuständigkeit des Handelsgerichts; gleichzeitig erhob er Widerklage. Mit Beschluss vom 2. Oktober 2012 trat das Handelsgericht auf die Klage und auf die Widerklage nicht ein (Dispositiv-Ziffer 1). Es setzte die Gerichtsgebühr fest (Dispositiv-Ziffer 2) und verteilte die Verfahrenskosten (Dispositiv-Ziffern 3 und 4). Das Handelsgericht stellte im Wesentlichen darauf ab, die Kläger hätten bereits vor dem Bezirksgericht Zürich mit Klage vom 1. September 2011 die Feststellung verlangt, dass die streitgegenständlichen Äusserungen des Beschwerdegegners ihre Persönlichkeitsrechte verletzten und hätten entsprechende Unterlassungs- und Publikationsbegehren gestellt. Zwar bestehe nach Art. 36 ZPO eine örtliche Zuständigkeit zur Beurteilung der geltend gemachten Ansprüche aus der Verletzung von Lauterkeitsrecht. Auch die sachliche Zuständigkeit erscheine gestützt auf Art. 5 Abs. 1 lit. d ZPO in Verbindung mit § 44 lit. a des Gesetzes des Kantons Zürich vom 10. Mai 2010 über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess (GOG/ZH) gegeben, wonach das Handelsgericht für Streitigkeiten nach dem UWG bei einem Fr. 30'000.-- übersteigenden Streitwert zuständig ist. Eine sachliche Zuständigkeit des Handelsgerichts führe allerdings dazu, dass derselbe Sachverhalt bezüglich der zum Teil gleichen Begehren einmal vom Bezirksgericht (betreffend die Verletzung des Persönlichkeitsrechts) und einmal vom Handelsgericht (betreffend die Verletzung von Lauterkeitsrecht) zu beurteilen wäre. Dies sei unerwünscht, weil der Sachverhalt so abhängig vom anwendbaren materiellen Recht zergliedert und vor verschiedene Instanzen gebracht werden müsste. C. Mit Beschwerde in Zivilsachen beantragen die Kläger dem Bundesgericht, es sei der Nichteintretensentscheid des Handelsgerichts des Kantons Zürich vom 2. Oktober 2012 in Bezug auf ihre Klage (nicht aber in Bezug auf die Widerklage des Beschwerdegegners) aufzuheben, und es sei die Sache zur materiellen Behandlung der Klage an die Vorinstanz zurückzuweisen. Eventualiter seien die Ziffern 3 und 4 des angefochtenen Entscheids aufzuheben und die Sache an die Vorinstanz zurückzuweisen mit der Weisung, die Gerichtskosten für das vorinstanzliche Verfahren auf die Obergerichtskasse zu nehmen sowie den Beschwerdeführern für das vorinstanzliche Verfahren aus der Obergerichtskasse eine angemessene Parteientschädigung auszurichten. Der Beschwerdegegner teilte dem Bundesgericht mit Eingabe vom 10. Dezember 2012 mit, er verzichte auf eine Beschwerdeantwort und verwies auf die Ausführungen im angefochtenen Entscheid. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. D. Mit Verfügung vom 26. November 2012 erteilte das Bundesgericht der Beschwerde die aufschiebende Wirkung.