Sachverhalt:
A. Am 14. Oktober 2008 stellte die Swisscom (Schweiz) AG ein Gesuch um Errichtung einer Mobilfunk-Basisstation auf dem Dach des Gebäudes auf Parzelle Nr. 6717 an der Tittwiesenstrasse 29 in Chur. Mit Entscheid vom 11. Januar 2010 wies der Stadtrat Chur die dagegen erhobenen Einsprachen ab, soweit er darauf eintrat, und erteilte die Baubewilligung unter Auflagen und Bedingungen.
Ein Teil der Einsprecher (darunter die im Rubrum aufgeführten Beschwerdeführer) erhoben gegen diesen Entscheid Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Sie machten insbesondere geltend, ihr Anspruch auf rechtliches Gehör sei verletzt worden, weil ihnen ein Schreiben vom 10. Dezember 2009 der Swisscom (Schweiz) AG an die Stadt Chur betreffend die Standortevaluation und das Mobilfunkkonzept für das Jahr 2010 vorenthalten worden sei.
Mit Urteil vom 7. September 2010 wies das Verwaltungsgericht die Beschwerde ab. Es erwog, die geltend gemachte Gehörsverletzung sei im Rahmen des Schriftenwechsels vor Verwaltungsgericht geheilt worden. Die übrigen Rügen, insbesondere bezüglich angeblicher weiterer Gehörsverletzungen, hielt es für unbegründet.
Eine gegen das Urteil des Verwaltungsgerichts eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten hiess das Bundesgericht mit Urteil 1C_50/2011 vom 11. August 2011 gut. Es bejahte darin eine Verletzung des Anspruchs auf rechtliches Gehör der Beschwerdeführer in Bezug auf ein nicht in den Akten enthaltenes Protokoll einer Besprechung vom 26. August 2009 zwischen der Stadt Chur und der Swisscom. Es hob das Urteil der Verwaltungsgerichts vom 7. September 2010 auf und wies die Angelegenheit zur Gewährung des rechtlichen Gehörs und zu neuem Entscheid an das Verwaltungsgericht zurück.
B. Im Rahmen der weiteren Behandlung der Streitsache stellte das Verwaltungsgericht fest, dass von der erwähnten Besprechung vom 26. August 2009 kein Protokoll existiert. Aus den von der Stadt Chur ins Recht gelegten Beilagen 14 - 21 sowie den Stellungnahmen der Swisscom und der Stadt Chur ergebe sich indessen das damalige Gesprächsthema. Das Festhalten der Beschwerdeführer an der Auffassung, eine qualifizierte Stellungnahme sei für sie unmöglich, weshalb die Verletzung des rechtlichen Gehörs nach wie vor bestehe, erweise sich vor diesem Hintergrund als unbegründet. Das Verwaltungsgericht hielt mit Urteil vom 27. Januar 2012 mangels anderweitiger neuer Erkenntnisse an seinem Entscheid vom 7. September 2010 fest und wies die Beschwerde ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 24. April 2012 beantragen die im Rubrum genannten Beschwerdeführer, das Urteil des Verwaltungsgerichts vom 27. Januar 2012 sei aufzuheben und die Angelegenheit sei zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Sie beschweren sich wiederum über eine Missachtung ihres Gehörsanspruchs.
Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werde. Die Stadt Chur und die Swisscom stellen Antrag auf Abweisung der Beschwerde. In ihrer Stellungnahme dazu halten die Beschwerdeführer im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest.
D. Mit Präsidialverfügung vom 30. Mai 2012 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung beigelegt.

Erwägungen:
1. Die Sachurteilsvoraussetzungen sind erfüllt und geben zu keinen Bemerkungen Anlass (vgl. Urteil des Bundesgerichts 1C_50/2011 vom 11. August 2011 E. 1.1). Auf die Beschwerde ist einzutreten.
2. Die Beschwerdeführer machen geltend, ihr Anspruch auf rechtliches Gehör (<ref-law>) sei missachtet worden. Von der Besprechung zwischen der Stadt Chur und der Swisscom vom 26. August 2009 seien weder ein Protokoll noch Gesprächsnotizen vorhanden. Entsprechend hätten sie keine Möglichkeit gehabt, zum Ergebnis dieser Besprechung Stellung zu nehmen. Eine Stellungnahme zu den eingereichten Dokumenten genüge nicht, um die Gehörsverletzung zu heilen.
2.1 Aus dem Anspruch auf ein faires Verfahren und auf rechtliches Gehör folgt das Recht der Parteien, Einsicht in die Akten eines hängigen Verfahrens zu nehmen und sich dazu zu äussern (Art. 29 Abs. 1 und 2 BV, Art. 6 Ziff. 1 EMRK). Das Akteneinsichtsrecht bezieht sich grundsätzlich auf sämtliche verfahrensbezogenen Akten; ausgenommen sind praxisgemäss rein interne Akten, die ausschliesslich für die interne Meinungsbildung bestimmt sind und denen kein Beweischarakter zukommt (<ref-ruling> E. 4a S. 474 f. mit Hinweisen). Nicht erforderlich ist, dass die Akten den Entscheid in der Sache tatsächlich beeinflussen können (<ref-ruling> E. 3.2 S. 389; Urteile des Bundesgerichts 1C_88/2011 vom 15. Juni 2011 E. 3.4 und 1C_50/2011 vom 11. August 2011 E. 2.2).
2.2 Bereits aus dem Urteil des Bundesgerichts 1C_50/2011 vom 11. August 2011 E. 2.4.3 ergibt sich, dass aus den Akten zu schliessen ist, dass die Besprechung vom 26. August 2009, wie auch jene vom 16. Dezember 2009 im Rahmen von regelmässigen Kontakten zwischen der Stadt Chur und den Mobilfunkbetreibern stattfand. Die Kontakte sind vor dem Hintergrund von Art. 18 Abs. 3 des Baugesetzes der Stadt Chur vom 26. November 2006 zu sehen. Nach dieser Bestimmung kann die Baubehörde Standorte festlegen und insbesondere von den Mobilfunkbetreibern ein Gesamtkonzept für die Erstellung ihrer Anlagen verlangen. Im Rahmen dieses Gesamtkonzepts bzw. des Dialogmodells zwischen der Stadt Chur und den schweizerischen Mobilfunkbetreibern geht es unter anderem auch darum, Alternativstandorte zu prüfen. Mithin geht es beim erwähnten Gesamtkonzept bzw. beim Dialogmodell um eine Planung, welche zwar über einzelne Bauprojekte hinausreicht, diese aber auch direkt beeinflussen kann, ja darauf ausgerichtet ist, steuernd auf diese einzuwirken. Dies bestätigt auch das Protokoll der Besprechung vom 16. Dezember 2009, welches sich primär mit dem Gesamtkonzept und dem Dialogmodell befasst, unter dem Titel "Weiteres Vorgehen" aber auch festhält, dass das pendente Gesuch der Swisscom für die Anlage an der Tittwiesenstrasse 29 mit zusätzlichen Unterlagen über die Standortevaluation ergänzt worden sei und vorbehältlich einer stadtinternen Prüfung bewilligt werden könne.
Im erwähnten Urteil 1C_50/2011 vom 11. August 2011 E. 2.4.3 ging das Bundesgericht davon aus, dass auch das Protokoll der Besprechung vom 26. August 2009 einen Bezug zum vorliegenden Baubewilligungsverfahren aufweise. Indirekt bestätige dies die Swisscom, wenn sie in ihrer Vernehmlassung an das Bundesgericht ausführe, dass die von den Beschwerdeführern monierten Aktenstücke und die Verhandlungen zwischen der Stadt Chur und Vertretern der drei Mobilfunkanbieter "grossmehrheitlich" mit dem Baugesuch in keinem relevanten Konnex stünden und dass es dabei inhaltlich "nur am Rande" um das Baugesuch gegangen sei.
2.3 Nachdem sich herausgestellt hatte, dass von der Besprechung vom 26. August 2009 kein Protokoll existiert, gelangte das Verwaltungsgericht aufgrund der Aussagen der Stadt Chur und der Swisscom zum Schluss, dass es in der Besprechung darum gegangen sei, die Differenzen in Bezug auf das Erfordernis einer Standortevaluation für die nachgesuchte Baubewilligung auszuräumen. Der Forderung nach einer Standortevaluation sei die Swisscom schliesslich am 10. Dezember 2009 nachgekommen, was für die Bewilligung des Vorhabens entscheidend gewesen sei.
Diese Würdigung des Verwaltungsgerichts stimmt mit den Verfahrensakten überein und ist nicht zu beanstanden. Soweit die Beschwerdeführer auf Widersprüche in den Angaben der Swisscom und der Stadt Chur hinweisen, ist diesen im Hinblick auf die hier umstrittene Baubewilligung keine entscheidende Bedeutung beizumessen.
2.4 Wie die Vorinstanz zutreffend ausführt, wurde die Standortevaluation vom 10. Dezember 2009 den Beschwerdeführern erst im verwaltungsgerichtlichen Verfahren R 10 20 (Urteil vom 7. September 2010) zur Kenntnis gebracht. Die Gehörsverletzung konnte indessen im Rahmen eines doppelten Schriftenwechsels im damaligen Beschwerdeverfahren durch das Verwaltungsgericht geheilt werden. Zudem wurde den Beschwerdeführern im zweiten Verfahren (R 10 20A) Gelegenheit zur Stellungnahme zu den von der Stadt Chur neu eingereichten Beilagen 14 - 21 gegeben. Damit erhielten diese umfassende Informationen über den Inhalt verschiedener Kontakte zwischen der Stadt Chur und der Swisscom. Die Vorinstanz hat mithin sämtliche Massnahmen ergriffen, um den Gehörsanspruch der Beschwerdeführer umfassend zu erfüllen, nachdem kein Protokoll der Besprechung vom 26. August 2009 vorgelegt werden konnte. Von einer Verweigerung des rechtlichen Gehörs kann unter diesen Umständen keine Rede sein.
3. Somit ist die Beschwerde abzuweisen. Die Gerichtskosten sind den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Diese haben der anwaltlich vertretenen Swisscom eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 2 und 5 in Verbindung mit <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die Swisscom (Schweiz) AG für das bundesgerichtliche Verfahren mit Fr. 1'500.-- unter solidarischer Haftbarkeit zu entschädigen.
4. Dieses Urteil wird den Beschwerdeführern, der Swisscom (Schweiz) AG, der Stadt Chur sowie dem Amt für Natur und Umwelt und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 4. Dezember 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Haag