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.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (Art. 29 Abs. 1 BGG; <ref-ruling> E. 1 mit Hinweisen).
1.1 Angefochten ist ein Endentscheid einer letzten kantonalen Instanz (Art. 75 Abs. 1 und Abs. 2 lit. a BGG i.V.m. Art. 5 Abs. 1 lit. d ZPO sowie Art. 90 BGG). Dagegen steht die Beschwerde in Zivilsachen offen. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist - unter Vorbehalt einer hinreichenden Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) - auf die Beschwerde einzutreten.
1.2 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Mit Blick auf die Begründungspflicht des Beschwerdeführers (Art. 42 Abs. 1 und 2 BGG) behandelt es aber grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind; es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2.2.1; <ref-ruling> E. 1.4.1; je mit Hinweisen). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG).
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substantiiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss Art. 105 Abs. 2 BGG gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre; andernfalls kann ein Sachverhalt, der vom im angefochtenen Entscheid festgestellten abweicht, nicht berücksichtigt werden. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3 S. 351 f., 393 E. 7.1 S. 398, 462 E. 2.4 S. 466 f.).
2. Die Beschwerdeführer werfen der Vorinstanz vor, sie habe sich in Verletzung von Art. 5 Abs. 1 lit. d und Art. 90 ZPO zu Unrecht für unzuständig erklärt.
2.1 Die Vorinstanz hat zunächst zutreffend erwogen, der Streitgegenstand sei nicht bereits beim Bezirksgericht rechtshängig, zumal mit Klage vom 1. September 2011 an das Bezirksgericht ausdrücklich Ansprüche aus der Verletzung des Persönlichkeitsrechts geltend gemacht und entsprechende Feststellungs- und Unterlassungsbegehren gestellt werden, während mit der vorliegend zu beurteilenden Klage insbesondere die Feststellung verlangt wird, dass bestimmte Äusserungen unlauter sind und eine widerrechtliche Verletzung der wettbewerbsrechtlichen Stellung der Beschwerdeführer darstellen.
Die Beschwerdeführer weisen jedoch zu Recht darauf hin, dass entgegen den Sachverhaltsdarstellungen im angefochtenen Entscheid nicht sie beide die Klage beim Bezirksgericht Zürich eingereicht haben, sondern nur der Beschwerdeführer 1. Insoweit fällt eine bereits bestehende Rechtshängigkeit beim Bezirksgericht nicht nur aufgrund des unterschiedlichen Streitgegenstands ausser Betracht; es fehlt hinsichtlich der Beschwerdeführerin 2 auch an der Identität der Parteien (vgl. Art. 64 Abs. 1 lit. a ZPO). Diesen Umstand lässt die Vorinstanz auch in ihren weiteren Erwägungen zur sachlichen Zuständigkeit ausser Betracht und stellt den Sachverhalt diesbezüglich unzutreffend dar. Es handelt sich dabei, worauf die Beschwerdeführer zutreffend hinweisen, um ein offensichtliches Versehen (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
2.2 Das kantonale Recht regelt die sachliche und funktionelle Zuständigkeit der Gerichte, soweit das Gesetz nichts anderes bestimmt (Art. 4 Abs. 1 ZPO). Diese Kompetenz zur Regelung der sachlichen Zuständigkeit wird unter anderem durch Art. 5 Abs. 1 lit. d ZPO insoweit eingeschränkt, als das kantonale Recht ein Gericht zu bezeichnen hat, das als einzige Instanz zuständig ist für Streitigkeiten nach dem Bundesgesetz vom 19. Dezember 1986 gegen den unlauteren Wettbewerb (UWG; SR 241), sofern der Streitwert mehr als Fr. 30'000.-- beträgt oder der Bund sein Klagerecht ausübt. Dabei muss es sich um ein oberes kantonales Gericht handeln (Art. 75 Abs. 2 lit. a BGG).
Der Kanton Zürich hat diese Vorgaben umgesetzt, indem er für derartige Streitigkeiten nach § 44 lit. a GOG/ZH in Verbindung mit Art. 6 Abs. 4 lit. a ZPO das Handelsgericht als einzige Instanz eingesetzt hat.
2.3 Der Vorinstanz ist nicht entgangen, dass für die zu beurteilende Streitigkeit nach dem UWG gemäss Art. 5 Abs. 1 lit. d ZPO in Verbindung mit § 44 lit. a GOG/ZH grundsätzlich das Handelsgericht sachlich zuständig ist. Sie hält es jedoch für unerwünscht, dass die verschiedenen Klageansprüche aus UWG einerseits und aus Persönlichkeitsrecht andererseits, denen im Wesentlichen derselbe Sachverhalt zugrunde liegt, von verschiedenen Instanzen beurteilt werden. Dabei verkennt sie zunächst, dass die Voraussetzungen, unter denen mehrere Klageansprüche zwischen denselben Parteien einem Gericht in einer einzigen Klage unterbreitet werden können (sog. Klagenhäufung), in Art. 90 ZPO geregelt sind. Danach "kann" die klagende Partei mehrere Ansprüche gegen dieselbe Partei in einer Klage vereinen, sofern das gleiche Gericht dafür zuständig ist (lit. a) und die gleiche Verfahrensart anwendbar ist (lit. b). Die Beschwerdeführer weisen zutreffend darauf hin, dass die Wahl, ob mehrere Ansprüche gegen dieselbe Partei in einer Klage vereint oder je separat geltend gemacht werden sollen, bei der klagenden Partei liegt. Ein Wahlrecht stand der klagenden Partei auch nach dem von der Vorinstanz erwähnten aArt. 12 Abs. 2 UWG (AS 1988 226 f.) zu; eine Verpflichtung, den Anspruch aus Verletzung des UWG nicht separat, sondern zusammen mit anderen im Zusammenhang stehenden Ansprüchen gerichtlich geltend zu machen, bestand jedoch unter dieser Bestimmung ebenfalls nicht.
Der Beschwerdeführer 1, der gegen den Beschwerdegegner beim Bezirksgericht Zürich bereits eine Klage auf Feststellung einer Persönlichkeitsverletzung eingereicht hatte, verzichtete allerdings auf eine Vereinigung mit dem vorliegend geltend gemachten Anspruch aus Verletzung des UWG in einer Klage; er reichte die Rechtsbegehren vielmehr je bei verschiedenen Gerichten ein. Soweit die Vorinstanz davon ausgeht, der Beschwerdeführer 1 hätte auch bezüglich des eingeklagten Anspruchs auf Feststellung einer UWG-Verletzung eine Wahl zugunsten des Bezirksgerichts getroffen, kann ihr nicht gefolgt werden.
Eine objektive Klagenhäufung fällt bei den vom Beschwerdeführer 1 mit zwei verschiedenen Klagen geltend gemachten Ansprüchen bereits aus diesem Grund ausser Betracht. Es braucht daher nicht vertieft zu werden, ob die weiteren Voraussetzungen für eine Klagenhäufung nach Art. 90 ZPO erfüllt wären. Immerhin ist darauf hinzuweisen, dass es an der gleichen sachlichen Zuständigkeit für beide Ansprüche fehlt (lit. a), ist für die Streitigkeit aus dem UWG doch von Bundesrechts wegen eine einzige kantonale Instanz vorgeschrieben (Art. 5 Abs. 1 lit. d ZPO), bei der es sich um ein oberes kantonales Gericht handeln muss (Art. 75 Abs. 2 lit. a BGG). Das von der Vorinstanz als zuständig erklärte Bezirksgericht erfüllt diese Voraussetzungen nicht.
Die Vorinstanz ist daher auf die Klage des Beschwerdeführers 1 zu Unrecht nicht eingetreten.
2.4 Inwiefern die Beschwerdeführerin 2 gezwungen sein soll, ihre auf eine angebliche Verletzung des UWG gestützte Klage gegen den Beschwerdegegner bei einem anderen als dem nach Art. 5 Abs. 1 lit. d ZPO in Verbindung mit § 44 lit. a GOG/ZH zuständigen Handelsgericht einzureichen, weil bereits beim Bezirksgericht Zürich ein anderer Anspruch des Beschwerdeführers 1 gegen den Beschwerdegegner eingeklagt wurde, legt die Vorinstanz nicht dar und leuchtet auch nicht ein. Bei der einfachen Streitgenossenschaft nach Art. 71 ZPO sind mehrere Personen - im Gegensatz zur notwendigen Streitgenossenschaft (Art. 70 ZPO) - nicht gezwungen, gemeinsam zu klagen. Noch weniger kann von der Beschwerdeführerin 2 verlangt werden, einen Anspruch gemeinsam mit dem Beschwerdeführer 1 beim Bezirksgericht einzuklagen, das für die Beurteilung von Streitigkeiten aus dem UWG nicht zuständig ist (vgl. Art. 5 Abs. 1 lit. d ZPO). Wie die Klagenhäufung setzt auch die einfache Streitgenossenschaft voraus, dass dasselbe Gericht für alle eingeklagten Ansprüche sachlich zuständig ist (vgl. <ref-ruling> E. 5.1 S. 480).
Die Vorinstanz hat sich auch für die Beurteilung der Klageansprüche der Beschwerdeführerin 2 zu Unrecht für unzuständig erklärt.
3. In Gutheissung der Beschwerde ist der angefochtene Entscheid aufzuheben, soweit auf die Klage nicht eingetreten wird, und die Sache ist zur materiellen Behandlung der Klage an die Vorinstanz zurückzuweisen. Der Beschwerdegegner hat keine Beschwerde erhoben und daher den Entscheid der Vorinstanz, auf seine Widerklage nicht einzutreten, unangefochten gelassen.
Der Beschwerdegegner hat im vorinstanzlichen Verfahren die Einrede der Unzuständigkeit erhoben und hat auch im Beschwerdeverfahren vor Bundesgericht auf den angefochtenen Entscheid verwiesen. Entgegen seinem Antrag hinsichtlich der Verfahrenskosten wird er bei diesem Verfahrensausgang kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. In Gutheissung der Beschwerde wird der angefochtene Beschluss des Handelsgerichts des Kantons Zürich vom 2. Oktober 2012 aufgehoben, soweit auf die Klage nicht eingetreten wird, und die Sache wird zur materiellen Behandlung der Klage an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten von Fr. 5'000.-- werden dem Beschwerdegegner auferlegt.
3. Der Beschwerdegegner hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt Fr. 6'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 15. April 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann