Sachverhalt: A. A.a. Z._ (Beschwerdegegner) betreibt unter der Firma "A._" ein Einzelunternehmen mit Sitz in B._. Das Unternehmen bezweckt die Ausführung von Aufträgen in den Bereichen Fotografie, visuelle Gestaltung und Innenarchitektur. X._ und Y._ (Beschwerdeführer) sind ausgebildete Ärzte und wohnen in S._. A.b. Am 27. November 2009 unterbreitete der Beschwerdegegner den Beschwerdeführern eine als "Angebot 091127" bezeichnete Offerte für den Umbau des Wohnhauses in S._. Am 18. Dezember 2009 reichte der Beschwerdegegner ein als "Auftragsbestätigung 09042-09001" bezeichnetes Formular nach. Dieses unterzeichneten die Beschwerdeführer am 20. Dezember 2009. Sowohl der Offerte als auch der Auftragsbestätigung waren allgemeine Geschäftsbedingungen (AGB) beigelegt, deren Ziffer 9.1 wie folgt lautet: "9.1 Gerichtsstand ist Oberwil. (...)." In der Folge kam es zwischen den Parteien zu einem Streit im Zusammenhang mit der Durchführung des Vertrages betreffend den Umbau des Wohnhauses. B. B.a. Mit Klage vom 22. Dezember 2011 beantragte der Beschwerdegegner dem Bezirksgericht Arlesheim, es seien die Beschwerdeführer in solidarischer Verbindung zur Zahlung von Fr. 31'928.30 nebst Zins zu 5 % seit dem 26. April 2011 sowie von Zahlungsbefehlskosten zu verurteilen. In ihrer Klageantwort vom 10. April 2012 machten die Beschwerdeführer unter anderem geltend, das Bezirksgericht Arlesheim sei mangels gültiger Gerichtsstandsvereinbarung örtlich nicht zuständig. Mit Verfügung vom 27. April 2012 beschränkte das Bezirksgericht das Verfahren vorläufig auf die Frage der örtlichen Zuständigkeit. Mit Zwischenentscheid vom 10. September 2012 bejahte das Bezirksgericht seine örtliche Zuständigkeit zur Beurteilung der Klage. B.b. Dagegen erhoben die Beschwerdeführer Berufung beim Kantonsgericht Basel-Landschaft. Mit Entscheid vom 12. März 2013 wies dieses die Berufung ab. C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht, es sei der Entscheid des Kantonsgerichts Basel-Landschaft vom 12. März 2013 aufzuheben und auf die Klage sei nicht einzutreten. Der Beschwerdegegner schliesst in seiner Vernehmlassung auf Nichteintreten, eventualiter Abweisung. Die Vorinstanz beantragt Abweisung. 