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.

Erwägungen:
1. Das angefochtene Urteil des Verwaltungsgerichts ist ein Endentscheid einer letzten kantonalen Instanz (Art. 82 lit. a i.V.m. Art. 86 Abs. 1 lit. d und Art. 90 BGG). Ihm liegt ein Beschwerdeverfahren über ein Baubegehren und damit eine öffentlich-rechtliche Angelegenheit zugrunde. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach Art. 82 lit. a BGG steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung (<ref-ruling> E. 1.2 S. 251, 400 E. 2.1 S. 404). Ausnahmegründe im Sinne von Art. 83 ff. BGG liegen nicht vor. Die Beschwerdeführer haben am Verfahren vor der Vorinstanz teilgenommen (Art. 89 Abs. 1 lit. a BGG). Sie sind als Nachbarn zur Beschwerde legitimiert (Art. 89 Abs. 1 lit. b und c BGG; ausführlich <ref-ruling> E. 2 S. 32; <ref-ruling> E. 1.3.3 S. 253). Auf die frist- und formgerecht eingereichte Beschwerde ist grundsätzlich einzutreten.
Soweit die Beschwerdeführer allerdings beantragen, es sei festzustellen, dass ihnen in einem zukünftigen Verfahren in der gleichen Sache vor dem Hochbauamt der Stadt Chur Parteistellung zukomme, fehlt es am erforderlichen Feststellungsinteresse, zumal die Frage einer allfälligen Ausnahmebewilligung ausserhalb des Streitgegenstands liegt. Insoweit ist auf die Beschwerde nicht einzutreten.
2.1 2.1.1 Die Vorinstanz hat erwogen, im vorliegenden Verfahren sei zu klären, ob die Stadt Chur die Baubewilligung mit Entscheid vom 11. Oktober 2010 zu Recht erteilt habe. Nicht Verfahrensgegenstand bildeten dagegen die Fragen der Wiederherstellung des rechtmässigen Zustands und der Ausfällung einer Busse. Diese beiden Aspekte seien Gegenstand eigener Verfahren und könnten - auch wenn es im Einzelfall der Effizienz dienlich sein könnte - nach den klaren gesetzlichen Vorgaben (Art. 94 KRG/GR zur Wiederherstellung des rechtmässigen Zustands und Art. 95 KRG/GR zur Busse) im Baubewilligungsverfahren nicht thematisiert werden. Soweit die Beschwerdeführer eine Abweichung der teilweise erstellten Mauer von den bewilligten Plänen rügten und die Rückversetzung der Mauer respektive die Wiederherstellung des ursprünglichen Zustands beantragten, könne deshalb auf die Beschwerde nicht eingetreten werden.
2.1.2 In materieller Hinsicht hat die Vorinstanz zusammenfassend ausgeführt, der Zweck des Bauvorhabens auf der Parzelle Nr. 4473 (Bruchsteinmauer in Form eines Mauerecks, Sonnensegel) liege insbesondere in der Schaffung eines Rückzugsorts begründet; gleichzeitig würden störende Emissionen und Immissionen vermindert. Hierzu genüge die Einfriedung des Sitzplatzes durch ein Mauereck gegen die Grundstücksgrenzen hin. Die geplante Bruchsteinmauer sei im Ergebnis als Teileinfriedung im Sinne von Art. 76 Abs. 4 KRG/GR zu qualifizieren. Unter Anwendung dieser Bestimmung resultiere ein Grenzabstand von 0,9 m, welcher gemäss den eingereichten Plänen eingehalten werde. Das Bauprojekt erweise sich damit als gesetzeskonform.
2.2 Die Beschwerdeführer machen geltend, die Vorinstanz sei zu Unrecht auf ihre Rüge, es bestehe eine Diskrepanz zwischen den eingereichten Plänen und den tatsächlichen Verhältnissen, nicht eingetreten. Der Abstand des in der Ausführung begriffenen Bauwerks zu ihrem Grundstück betrage bloss 27 cm, womit der zulässige Grenzabstand massiv unterschritten werde. Es widerspreche dem Gebot der (Kosten-)Effizienz bzw. dem Grundsatz der Verhältnismässigkeit, eine Wiederherstellung erst nach Beendigung der Erstellung anzuordnen. Die Vorinstanz sei im Ergebnis in Willkür und in überspitzten Formalismus verfallen, indem sie auf ihre Beschwerde teilweise nicht eingetreten sei und sie (die Beschwerdeführer) auf ein getrennt zu führendes Wiederherstellungsverfahren verwiesen habe. Zugleich habe die Vorinstanz hierdurch Art. 22 Abs. 1 RPG verletzt.
2.2 Die Beschwerdeführer machen geltend, die Vorinstanz sei zu Unrecht auf ihre Rüge, es bestehe eine Diskrepanz zwischen den eingereichten Plänen und den tatsächlichen Verhältnissen, nicht eingetreten. Der Abstand des in der Ausführung begriffenen Bauwerks zu ihrem Grundstück betrage bloss 27 cm, womit der zulässige Grenzabstand massiv unterschritten werde. Es widerspreche dem Gebot der (Kosten-)Effizienz bzw. dem Grundsatz der Verhältnismässigkeit, eine Wiederherstellung erst nach Beendigung der Erstellung anzuordnen. Die Vorinstanz sei im Ergebnis in Willkür und in überspitzten Formalismus verfallen, indem sie auf ihre Beschwerde teilweise nicht eingetreten sei und sie (die Beschwerdeführer) auf ein getrennt zu führendes Wiederherstellungsverfahren verwiesen habe. Zugleich habe die Vorinstanz hierdurch Art. 22 Abs. 1 RPG verletzt.
2.3 2.3.1 Die Ausführungen der Vorinstanz sind zutreffend. Aus Art. 94 und 95 KRG/GR ergibt sich, dass die Fragen der allfälligen Wiederherstellung des rechtmässigen Zustands und der Bestrafung der Bauherrschaft mit einer Busse in getrennt vom Baubewilligungsverfahren durchzuführenden Verfahren zu klären sind. Eine allfällige Nichtbeachtung der bewilligten Pläne führt mit anderen Worten nicht zur nachträglichen Verweigerung oder Aufhebung der Baubewilligung, sondern zu einem Wiederherstellungs- und einem Baubussverfahren. Dementsprechend können die Beschwerdeführer aus der (nach dem Einspracheentscheid vom 11. Oktober 2010) vorgenommenen Vermessung der teilweise erstellten Bruchsteinmauer vorliegend nichts zu ihren Gunsten ableiten. Die Vorinstanz ist folglich weder in Willkür noch in überspitzten Formalismus verfallen, indem sie im Baubewilligungsverfahren einzig die Rechtmässigkeit der gestützt auf die eingereichten Baupläne erteilten nachträglichen Baubewilligung überprüft hat und auf die weiteren Rügen der Beschwerdeführer nicht eingetreten ist. Dass ein anderes Vorgehen im Einzelfall effizienter sein mag, ändert hieran nichts.
2.3.2 Die Beschwerdeführer erheben keine Einwände gegen die materielle Beurteilung durch die Vorinstanz (vgl. E. 2.1.2 hiervor). Sie stellen in ihrer Beschwerde ans Bundesgericht weder die Qualifikation des Bauvorhabens als Teileinfriedung im Sinne von Art. 76 Abs. 4 KRG/GR in Frage, noch bringen sie vor, der sich aus der Anwendung dieser Bestimmung ergebende Grenzabstand von 0,9 m sei gemäss den von der Beschwerdegegnerin eingereichten Bauplänen nicht eingehalten. Vielmehr machen die Beschwerdeführer in der Sache einzig geltend, der angefochtene Entscheid verletze Art. 22 Abs. 1 RPG, wonach Bauten und Anlagen nur mit behördlicher Bewilligung errichtet oder geändert werden dürfen. Die Rüge ist nicht stichhaltig, da der Beschwerdegegnerin eine nachträgliche Baubewilligung für ihr Bauvorhaben (mit einem Grenzabstand von 0,9 m) erteilt wurde.
2.3.3 Entgegen den Ausführungen in der Beschwerde ist schliesslich nicht zu beanstanden, dass die Vorinstanz die Kosten des kantonalen Beschwerdeverfahrens den im Ergebnis vollumfänglich unterliegenden Beschwerdeführern auferlegt hat.
3. Die Beschwerde ist damit abzuweisen, soweit darauf eingetreten werden kann. Aufgrund ihres Unterliegens sind die bundesgerichtlichen Kosten den Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 BGG). Diese haben der privaten Beschwerdegegnerin eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG), wofür sie solidarisch haften (Art. 68 Abs. 4 BGG i.V.m. Art. 66 Abs. 5 BGG). Den in ihrem amtlichen Wirkungskreis obsiegenden Behörden ist keine Parteientschädigung zuzusprechen (Art. 68 Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- unter solidarischer Haftung zu entschädigen.
4. Dieses Urteil wird den Parteien, der Stadt Chur und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 6. Oktober 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner