Sachverhalt: A. Z._ ist Eigentümerin der Parzelle Nr. 4473 in Chur. An dieses Grundstück grenzt die Parzelle Nr. 4531, welche im Eigentum von X._ und Y._ steht. Mit Schreiben vom 30. Juni 2010 teilte die Stadt Chur Z._ mit, die Baupolizei habe am 28. Juni 2010 festgestellt, dass auf ihrer Parzelle in Missachtung baupolizeilicher Vorschriften ohne Baubewilligung eine Einfriedung (Bruchsteinmauer) erstellt werde und eine Gartenumgestaltung stattfinde. Die Stadt Chur forderte Z._ auf, zur Angelegenheit schriftlich Stellung zu nehmen und ein nachträgliches Baugesuch einzureichen. Am 19. Juli 2010 stellte Z._ ein nachträgliches Baugesuch für die Errichtung einer Bruchsteinmauer von 1,4 m Höhe auf der bestehenden Zyklopenmauer sowie für eine Gartenumgestaltung (Sitzplatz, Sonnensegel). Gemäss den eingereichten Plänen soll die Bruchsteinmauer auf der Parzelle Nr. 4473 im Abstand von 0,9 m zur Grenze der Parzelle Nr. 4531 zu stehen kommen. Das nachträgliche Baugesuch wurde vom 30. Juli bis zum 18. August 2010 öffentlich aufgelegt. Am 18. August 2010 erhoben X._ und Y._ Einsprache mit dem Antrag, das aufgelegte Bauprojekt sei den geltenden Vorschriften über den Grenzabstand anzupassen. Mit Beschluss vom 11. Oktober 2010 erteilte die Stadt Chur Z._ die nachträgliche Baubewilligung unter mehreren Auflagen. Die Einleitung eines Baubussverfahrens für die Ausführung von Bauarbeiten ohne Bewilligung wurde ausdrücklich vorbehalten. Gleichzeitig wies die Stadt Chur die Einsprache von X._ und Y._ ab. Die Stadt Chur erwog, anwendbar sei Art. 76 Abs. 4 des Raumplanungsgesetzes für den Kanton Graubünden (KRG/GR; BR 801.100), wonach Einfriedungen wie Zäune, Mauern und Holzwände bis zu einer Höhe von 1,5 m ab gewachsenem Boden an die Grundstücksgrenze gestellt werden könnten. Höhere Einfriedungen seien um das Mass der Mehrhöhe bis maximal 2,5 m zurückzuversetzen. Hier betrage die Höhe der gesamten Einfriedung 2,4 m. Die Mauer sei damit um die Mehrhöhe von 0,9 m von der Grenze zurückzusetzen. Da dieser Abstand gemäss den eingereichten Bauplänen eingehalten werde, erweise sich die von den Einsprechern vorgetragene Rüge der Grenzabstandsverletzung als unbegründet, weshalb die Einsprache abzuweisen sei. B. Gegen den Einspracheentscheid der Stadt Chur vom 11. Oktober 2010 erhoben X._ und Y._ am 15. November 2010 Beschwerde ans Verwaltungsgericht des Kantons Graubünden. Am 24. November 2010 wurde die teilerstellte Mauer auf der Parzelle Nr. 4473 durch das Vermessungsamt der Stadt Chur aufgenommen. Dabei ergab sich gegenüber der Parzelle Nr. 4531 ein Grenzabstand von 27 cm. Am 4. April 2011 führte das Verwaltungsgericht einen Augenschein vor Ort mit Beteiligung aller Parteien durch. Mit Urteil vom 5. April 2011 wies das Verwaltungsgericht die Beschwerde ab, soweit es auf diese eintrat. C. X._ und Y._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht mit den Anträgen, das Urteil des Verwaltungsgerichts aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Des Weiteren beantragen sie, es sei festzustellen, dass ihnen in einem allfälligen Verfahren um eine Ausnahmebewilligung vor dem Hochbauamt der Stadt Chur Parteistellung zukomme. Mit Verfügung vom 14. Juli 2011 wies der Präsident der I. öffentlich-rechtlichen Abteilung das von den Beschwerdeführern gestellte Gesuch um Gewährung der aufschiebenden Wirkung ab. Das Verwaltungsgericht, die Stadt Chur und Z._ beantragen in ihren Vernehmlassungen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Beschwerdeführer halten in ihren Stellungnahmen vom 30. August und 7. September 2011 an ihrem Standpunkt fest. 