Sachverhalt: A. Die B._ AG (nachfolgend: Vermieterin, Beschwerdegegnerin) schloss mit A._ und 25 weiteren Personen (nachfolgend: Mieter, Beschwerdeführer) im Frühjahr/Sommer 2012 Mietverträge über 16 Wohnungen in U._ ab. Dabei handelte es sich um Erstvermietungen. Die Mietverhältnisse wurden zwischen dem 15. Mai 2012 und dem 1. Oktober 2012 angetreten. In den Mietverträgen wurden Akontozahlungen in der Höhe von Fr. 280.-- bis Fr. 360.-- pro Monat für die ausgeschiedenen Nebenkosten vereinbart. Anfangs Juni 2014 kündigte die Vermieterin alle Mietverhältnisse ordentlich per 30. September 2014 und stellte den Mietern die Heiz- und Nebenkostenabrechnung für die Abrechnungsperiode 2012/2013 zu. Mitte Oktober 2014 folgte die Heiz- und Nebenkostenabrechnung für die Abrechnungsperiode 2013/2014. Die Saldi der Heiz- und Nebenkostenabrechnungen für die Abrechnungsperioden 2012/2013 und 2013/2014 überstiegen die von den Mietern geleisteten Akontozahlungen erheblich. In der Folge weigerten sich die Mieter, die von der Vermieterin geltend gemachten Nachforderungen für die effektiv angefallenen Nebenkosten in dem von ihr geforderten Umfang zu bezahlen. Unbestrittenermassen erkundigten sich die Mieter im Rahmen der Vertragsverhandlungen nie bei der Vermieterin, ob die vertraglich verlangten Akontozahlungen kostendeckend sein würden. Die Vermieterin machte den Mietern auch keine dahingehende Zusicherungen. B. Anlässlich der Schlichtungsverhandlung vom 20. Juli 2015 anerkannten die Mieter eine Nachzahlungspflicht in der Höhe von 20 % der geleisteten Akontobeträge für Heiz-/Nebenkosten. Am 11. September 2015 erhob die Vermieterin für die restlichen Forderungsbeträge gemäss den beiden Nebenkostenabrechnungen Klagen gegen die Mieter beim Mietgericht des Bezirks Horgen. Die verschiedenen Verfahren wurden mit Beschluss des Mietgerichts vereinigt. Mit Urteil vom 26. September 2017 hiess das Mietgericht die Klage der Vermieterin teilweise gut. Soweit die verlangten Nachzahlungen den Umfang von 30 % der in den jeweiligen Mietverträgen vereinbarten jährlichen Akontozahlungen überstiegen, wies es die Klage ab. Eine gegen dieses Urteil gerichtete Berufung der Vermieterin hiess das Obergericht des Kantons Zürich mit Urteil vom 30. April 2018 gut. Es verpflichtete die Mieter im Wesentlichen, der Vermieterin die jeweils auf ihre Wohnung entfallenden Nebenkosten gemäss den betragsmässig anerkannten Heiz- und Nebenkostenabrechnungen zu zahlen, und zwar im vollen Umfang des Saldos nach Abzug der bereits geleisteten Akontozahlungen. C. Mit Beschwerde in Zivilsachen beantragen die Mieter dem Bundesgericht, das Urteil des Obergerichts aufzuheben und das Urteil des Mietgerichts zu bestätigen. Die Beschwerdegegnerin trägt auf kostenfällige Abweisung der Beschwerde an, soweit darauf einzutreten sei. Das Obergericht hat auf Vernehmlassung verzichtet. Das Gesuch der Beschwerdeführer um Erteilung der aufschiebenden Wirkung wurde mit Präsidialverfügung vom 22. August 2018 gutgeheissen.