Sachverhalt: A. Mit Eingabe vom 11. März 2013 reichten B.A._ und A.A._ (Beschwerdeführer) sowie die D._ LLC, eine Gesellschaft mit Sitz in U._, beim Kantonsgericht Zug Klage gegen die C._ AG (Beschwerdegegnerin) ein. Die Klagebegehren lauteten wie folgt: "1. Der Beschluss des Verwaltungsrats vom 4. Juli 2013 der C._ AG, Zug ist nichtig. 2. Der Beschluss der Generalversammlung vom 29. Juli 2013 der C._ AG, Zug ist nichtig. 3. Gebühren, Spesen und Parteientschädigungen sowie die Kosten für den Versöhnungsversuch zu Lasten der Gegenpartei." In Ergänzung zur Klage hielten B.A._ und A.A._ sowie die D._ LLC auf Aufforderung des Gerichtspräsidenten fest, der Streitwert betrage EUR 2'975'991.97 betreffend die Dividenden der Geschäftsjahre 2011/12 und 2012/13, die an die D._ LLC ausgeschüttet werden sollten. In ihrer Replik vom 21. November 2014 präzisierten sie ihre Anträge dahingehend, dass die angefochtenen Beschlüsse des Verwaltungsrats und der Generalversammlung zu annullieren seien. Mit Entscheid vom 9. Juni 2016 trat das Kantonsgericht androhungsgemäss nicht auf die Klage der D._ LLC ein, nachdem letztere die auf Antrag der C._ AG angeordnete Sicherheit für die Parteientschädigung in der Höhe von Fr. 95'000.-- innert der letzten Nachfrist nicht geleistet hatte. Am 5. Mai 2017 zogen B.A._ und A.A._ die Klage zurück. Mit Entscheid vom 18. Mai 2017 schrieb das Kantonsgericht das Verfahren ab. Es auferlegte B.A._ und A.A._ die Gerichtskosten in der Höhe von Fr. 20'000.-- und verpflichtete sie zur Leistung einer Parteientschädigung in der Höhe von Fr. 72'370.25, beides unter solidarischer Haftbarkeit. Diesen Kostenentscheid fochten B.A._ und A.A._ beim Obergericht des Kantons Zug an. Das Obergericht reduzierte in seinem Urteil vom 26. Oktober 2017 die erstinstanzliche Parteientschädigung geringfügig auf Fr. 71'045.90 und wies die Beschwerde im Übrigen ab, unter Kosten und Entschädigungsfolgen zu Lasten von B.A._ und A.A._. B. B.A._ und A.A._ haben gegen das Urteil des Obergerichts Beschwerde in Zivilsachen erhoben. Damit beantragen sie was folgt: "1. Die Beschwerde wird gutgeheissen. 1.1. Folglich werden die Parteientschädigung auf CHF 11'472.- (incl. MWST und Spesen) und Gerichtskosten des ersten Entscheid[s] auf CHF 6'000,- festgesetzt 2. Gebühren, Kosten und Parteientschädigungen der zweiten und dieser Instanz gehen zu Lasten der Gegenpartei" Die C._ AG begehrt, die Beschwerde sei vollumfänglich abzuweisen, soweit darauf einzutreten sei. Das Obergericht beantragt ebenfalls die Abweisung der Beschwerde, soweit darauf eingetreten werden kann, unter Verzicht auf eine Vernehmlassung und Verweis auf die Erwägungen im angefochtenen Entscheid. Die Parteien replizierten und duplizierten. Mit Präsidialverfügung vom 22. Februar 2018 wurde das Gesuch um Erteilung der aufschiebenden Wirkung abgewiesen und auf den Antrag der C._ AG um Anordnung einer Verfügungsbeschränkung auf einem Grundstück von B.A._ nicht eingetreten.