Sachverhalt: A. A.a. Auf dem Grundstück Nr. xxx, Einwohnergemeinde (EG) U._, befindet sich die Wohnliegenschaft "C._", an der Stockwerkeigentum besteht. Die "C._" grenzt an das Grundstück Nr. yyy, welches im Eigentum der Baugesellschaft D._ steht. Auf diesem Grundstück befinden sich unmittelbar an die "C._" angrenzend drei von deren Bewohnern genutzte Parkplätze. Für diese Parkplätze erteilte die Baukommission der EG U._ am 10. September 2012 eine nachträgliche Baubewilligung, wogegen A.A._ und B.A._ (Beschwerdeführer) erfolglos bis ans Bundesgericht gelangten (vgl. Urteil 1C_244/2014 vom 11. November 2014). Bei diesen handelt es sich um die Eigentümer des Grundstücks Nr. zzz, über das der E._weg führt. Die von den Bewohnern der "C._" benutzten Parkplätze sind von der F._strasse (Hauptstrasse) her allein über den E._weg befahrbar, wobei ein grosser Teil der Zufahrt über diesen Weg führt. Im Grundbuch sind zugunsten des Grundstücks Nr. xxx ein "Benützungsrecht an der Zufahrtsstrasse zulasten Grundstück Nr. zzz" sowie ein "Zufahrts-, Zugangs- und Parkplatzbenutzungsrecht" zulasten des Grundstücks Nr. yyy eingetragen. Ausserdem besteht zugunsten des Grundstücks Nr. zzz und zulasten des Grundstücks Nr. yyy ein Bauverbot. A.b. Die Ausübung des auf dem Grundstück Nr. zzz lastenden Benützungsrechts führte zwischen A.A._ und B.A._ sowie den Miteigentümern der "C._" zu Streitigkeiten. Am 30. November 2015 machten A.A._ und B.A._ beim Vermittleramt Region Plessur ein Schlichtungsverfahren anhängig, das erfolglos blieb. Mit Klage vom 18. März 2016 gegen die Stockwerkeigentümergemeinschaft "C._" (Beschwerdegegnerin) ersuchten sie das heutige Regionalgericht Plessur zusammengefasst darum, dieser zu verbieten, den E._weg als Zufahrt sowie das Grundstück Nr. yyy als Parkplatz für Fahrzeuge zu nutzen. Eventuell sei festzustellen, dass keine Zufahrtsberechtigung über den E._weg und keine Berechtigung zur Nutzung des Parkplatzes bestehe. Mit Entscheid vom 11. Juli 2017 wies das Regionalgericht die Klage ab. B. Die von A.A._ und B.A._ gegen diesen Entscheid eingereichte Berufung wies das Kantonsgericht von Graubünden mit Urteil vom 26. November 2018 (eröffnet am 29. November 2018) ab, soweit es darauf eintrat. C. Mit Beschwerde in Zivilsachen vom 14. Januar 2019 (Poststempel) gelangen A.A._ und B.A._ ans Bundesgericht. Sie beantragen, es sei das Urteil des Kantonsgerichts aufzuheben und der Stockwerkeigentümergemeinschaft "C._" sowie allen in ihrer Verantwortung liegenden Personen (Verwandte, Freunde, Bekannte, Feriengäste und sonstige Dritte) unter Androhung der Straffolgen von Art. 292 StGB zu verbieten, den E._weg als Zufahrt zur Parzelle Nr. yyy zu benützen. Eventualiter sei der Stockwerkeigentümergemeinschaft und den genannten Personen unter Androhung der Straffolgen von Art. 292 StGB zu verbieten, die Parzelle Nr. yyy als Parkierungsanlage für Fahrzeuge zu nutzen. Subeventualiter sei die Sache zur Ergänzung und Untersuchung des Sachverhalts bzw. zur Neubeurteilung im Sinne der Erwägungen an das Kantonsgericht zurückzuweisen. Ausserdem ersuchen A.A._ und B.A._ das Bundesgericht darum, über ihre Beschwerde in einer öffentlichen Beratung zu entscheiden. Das Bundesgericht hat die Akten des kantonalen Verfahrens, indes keine Vernehmlassungen eingeholt.