Sachverhalt: A. Zwischen der Q._ AG als Arbeitgeberin (Beschwerdegegnerin) und den drei Personalverbänden Verband X._ (Beschwerdeführer 1), Verband Y._ (Beschwerdeführer 2), und Gewerkschaft Z._ (Beschwerdeführerin 3), besteht Uneinigkeit über die Arbeitszeitregelung bei Arbeitsübergabe. B. Gestützt auf die Schiedsklausel in Ziff. 2.4 des Gesamtarbeitsvertrags Q._ vom 4. Juli 2011 (nachfolgend: GAV) erhoben die Personalverbände am 12. September 2012 Schiedsklage gegen die Q._ AG bei einem Fünferschiedsgericht mit Sitz in Kreuzlingen. Sie beantragten, es sei festzustellen, dass bei jeder Dienstübergabe des Lokpersonals Überlappungszeit zu gewähren sei. Die Q._ AG beantragte die Abweisung dieses Begehrens. Am 24. Juni 2013 erging folgender Schiedsspruch: "1. Die Klage wird teilweise geschützt und festgestellt, dass bei jeder Arbeitsübergabe dem übernehmenden und dem übergebenden Lokführer Überlappungszeit wie folgt zu gewähren ist, a. je fünf Minuten, wenn der Zugsaufenthalt 5 Minuten dauert. Dies ist mit der praktizierten Arbeitszeitregelung erfüllt. b. je mindestens fünf Minuten, wenn der Zugsaufenthalt 5 Minuten überschreitet. Dies ist mit der praktizierten Arbeitszeitregelung nicht erfüllt. Das Arbeitsende des übergebenden Lokführers ist mit entsprechender Zeiteinteilung soweit hinauszuschieben, bis 5' Überlappungszeit erreicht sind, oder der Arbeitsbeginn des übernehmenden Lokführers ist mit entsprechender Zeiteinteilung soweit vorzuziehen, bis 5' Überlappungszeit erreicht sind. c. je mindestens die Dauer des Zugaufenthalts, wenn der Zugsaufenthalt 5 Minuten unterschreitet. Dies ist mit der praktizierten Arbeitszeitregelung erfüllt. (2.-4. Kosten, Parteientschädigungen, Mitteilung.) " C. Mit Beschwerde in Zivilsachen beantragen die Personalverbände dem Bundesgericht sinngemäss, es sei der Schiedsspruch vom 24. Juni 2013 aufzuheben und es sei die Sache zur Neubeurteilung an das Schiedsgericht zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz verzichtete auf Vernehmlassung. Die Beschwerdeführer reichten unaufgefordert eine Replik ein. 