Sachverhalt:
A. A.X._ (geb. 1964) stammt aus Sri Lanka. Er reiste im Jahr 1984 in die Schweiz ein. 1987 heiratete er die Schweizer Bürgerin Z._. Aus dieser Ehe gingen die Kinder V.Z._ (geb. 1988) und W.Z._ (geb. 1991) hervor. Die Ehe wurde im Jahr 1994 geschieden.
Am 15. Oktober 2000 heiratete A.X._ in Sri Lanka die Schweizer Bürgerin B.X._ (geb. 1972). Aus dieser Verbindung sind die drei Kinder hervorgegangen: C.X._ (geb. 1992), D.X._ (geb. 2005) und E.X._ (geb. 2010). A.X._ war im Besitz der Aufenthaltsbewilligung, welche ihm letztmals bis zum 1. März 2009 verlängert wurde.
Während seines Aufenthalts ist A.X._ wie folgt straffällig worden:
Mit Strafmandat vom 19. Februar 1993 verurteilte ihn das Kreisamt Chur wegen grober Verletzung der Verkehrsregeln zu einer Busse in der Höhe von Fr. 500.--.
Mit Urteil vom 17. März 1994 verurteilte ihn das Kreisgericht Chur wegen mehrfacher Veruntreuung zu drei Monaten Gefängnis bedingt.
Daraufhin verwarnte die Fremdenpolizei des Kantons Graubünden A.X._ und teilte ihm mit Verfügung vom 11. Mai 1994 mit, dass seine Aufenthaltsbewilligung bei einer allfälligen weiteren strafrechtlichen Verurteilung erlöschen würde. Nach der ausländerrechtlichen Verwarnung wurde A.X._ wie folgt straffällig:
Am 16. Mai 2007 verurteilte ihn das Kreispräsidium Chur wegen Unterlassens der Buchführung sowie wegen Vergehens gegen das Bundesgesetz über die Alters- und Hinterlassenenversicherung (Bundesgesetz vom 20. Dezember 1946 über die Alters- und Hinterlassenenversicherung vom 20. Dezember 1946; AHVG [SR 831.10]) zu einer Geldstrafe von 30 Tagessätzen bei einer Probezeit von zwei Jahren sowie einer Busse von Fr 1'000.--.
Am 26. Februar 2008 verurteilte ihn das Kreispräsidium Chur wegen Vergehen gegen das AHVG sowie Unterlassens der Buchführung zu einer Geldstrafe zu 20 Tagessätzen bei einer Probezeit von zwei Jahren sowie einer Busse von Fr. 800.--.
Am 21. Januar 2010 verurteilte ihn das Bezirksgericht Plessur wegen Tätlichkeit, Drohung, mehrfacher sexueller Handlungen mit Kindern, mehrfachen Versuchs der sexuellen Handlungen mit Kindern, mehrfacher Pornografie, Pornografie gemäss Art. 197 Ziff. 3bis StGB, mehrfachen Inzests zum Nachteil der Tochter C.X._ und wegen mehrfachen Versuchs des Inzests zu einer Freiheitsstrafe von drei Jahren und für die Tätlichkeiten zu einer Busse von Fr. 200.--.
Am 4. Februar 2011 verurteilte ihn die Staatsanwaltschaft Graubünden erneut wegen Unterlassens der Buchführung und Widerhandlung gegen das AHVG. Die bedingt ausgesprochenen Geldstrafen vom 16. Mai 2007 und 26. Februar 2008 wurden widerrufen und für vollziehbar erklärt.
A.X._ befand sich vom 24. Januar 2011 bis zum 22. Februar 2012 im Strafvollzug.
B. Mit Verfügung vom 12. September 2011 verweigerte das Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden die Verlängerung der Jahresaufenthaltsbewilligung von A.X._ und ordnete an, er habe die Schweiz nach Beendigung des Strafvollzugs zu verlassen. Eine gegen diese Verfügung erhobene Eingabe von A.X._ und B.X._ beim Departement für Justiz, Sicherheit und Gesundheit Graubünden blieb erfolglos. Die hiergegen gerichtete Beschwerde an das Verwaltungsgericht des Kantons Graubünden wies dieses mit Urteil vom 19. Juni 2012 ab.
C. Mit Eingabe vom 13. September 2012 beantragen A.X._ und B.X._ (Beschwerdeführende bzw. Beschwerdeführer 1 und Beschwerdeführerin 2) dem Bundesgericht, das Urteil vom 19. Juni 2012 sei aufzuheben; die Aufenthaltsbewilligung von A.X._ sei zu verlängern. Zudem ersuchen sie um Gewährung der unentgeltlichen Rechtspflege für die vorinstanzlichen und für das vorliegende Verfahren.
Das Verwaltungsgericht des Kantons Graubünden hat innert Frist keine Vernehmlassung eingereicht. Das Bundesamt für Migration beantragt, die Beschwerde sei abzuweisen. Das Departement für Justiz, Sicherheit und Gesundheit Graubünden hat sich nicht vernehmen lassen.
Mit Verfügung vom 19. September 2012 hat das präsidierende Mitglied der Beschwerde aufschiebende Wirkung zuerkannt.
Erwägungen:
1. 1.1 Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide ausgeschlossen, welche Bewilligungen betreffen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (Art. 83 lit. c Ziff. 2 BGG). Für das Eintreten genügt, wenn die ausländische Person dartut, dass potenziell ein Anspruch auf die beantragte Bewilligung besteht; ob die jeweiligen Voraussetzungen erfüllt sind, bildet Gegenstand der materiellen Beurteilung (BGE 136 II 177 E. 1.1 S. 179 f., 497 E. 3.3 S. 500 f.). In der Beschwerde wird in vertretbarer Weise ein Anspruch des Beschwerdeführers 1 nach Art. 42 Abs. 1 des Bundesgesetzes über die Ausländerinnen und Ausländer (AuG; SR 142.20) bzw. eine Verletzung von Art. 8 Ziff. 1 EMRK und Art. 13 Abs. 1 BV geltend gemacht; auf die Beschwerde ist dementsprechend einzutreten (vgl. BGE 135 II 1 E. 1.1 S. 4 ff.).
1.2 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 97 Abs. 1 BGG bzw. Art. 105 Abs. 2 BGG).
1.3 Trotz der Rechtsanwendung von Amtes wegen prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Begründungspflicht (Art. 42 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (BGE 135 II 384 E. 2.2.1 S. 389; 134 III 102 E. 1.1 S. 104; 133 II 249 E. 1.4.1 S. 254). Die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht untersucht es in jedem Fall nur, soweit eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG).
2. Die Beschwerdeführenden machen eine Verletzung von Art. 29 Abs. 2 BV geltend. Indem die Vorinstanz ihnen wie auch weiteren vorgeschlagenen Zeuginnen keine Gelegenheit gegeben habe, sich zur aktuellen Beziehung von C.X._ zum Beschwerdeführer 1 zu äussern und darzulegen, dass sie ihrem Vater mittlerweile verziehen habe, liege eine Gehörsverletzung vor.
2.1 Aus dem verfassungsrechtlichen Anspruch auf rechtliches Gehör gemäss Art. 29 Abs. 2 BV ergibt sich für die Parteien das Recht, Beweisanträge zu stellen, und für die Behörden die Pflicht, rechtzeitig und formgültig angebotene Beweisbegehren entgegenzunehmen und zu berücksichtigen (vgl. BGE 127 I 54 E. 2b S. 56). Das Gericht kann jedoch Beweisanträge ohne Verletzung des rechtlichen Gehörs ablehnen, wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener (antizipierter) Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde. Ebenso müssen keine Beweise abgenommen werden, wenn die Anträge nicht erhebliche Tatsachen betreffen (BGE 134 I 140 E. 5.3 S. 148; 131 I 153 E. 3 S. 157; 130 II 425 E. 2.1 S. 428; 124 I 208 E. 4a S. 211; je mit Hinweisen).
2.2 Eine Gehörsverletzung ist nicht dargetan: Die Vorinstanz hat sich gestützt auf die Aktenlage das für die Überprüfung der Nichtverlängerung der Aufenthaltsbewilligung erforderliche Bild über die familiären Verhältnisse des Beschwerdeführers 1 machen können. Den Antrag, Zeuginnen zum aktuellen Verhältnis von C.X._ zu ihrem Vater zu hören, musste die Vorinstanz nicht zulassen: Das Verschulden des Beschwerdeführers 1 wie auch das öffentliche Interesse bemisst sich nach der gegen ihn ausgesprochenen Freiheitsstrafe (vgl. unten E 3.1 ff.). Eine angebliche Verzeihung durch das Opfer, die notabene durch Drittpersonen bezeugt werden soll, ist nicht geeignet, das Verschulden des Täters zu relativieren und ebenso wenig, das öffentliche Interesse an seiner Fernhaltung abzumildern (vgl. unten E. 4). Die antizipierte Beweiswürdigung durch die Vorinstanz ist nachvollziehbar und nicht willkürlich (BGE 134 I 140 E. 5.3 S. 148; 131 I 153 E. 3 S. 157; Urteil 2C_157/2013 vom 22. Februar 2013 E. 3.3).
3. 3.1 Gemäss Art. 51 Abs. 1 AuG erlöschen die Ansprüche nach Art. 42 AuG (oben E. 1.1), wenn sie rechtsmissbräuchlich geltend gemacht werden (lit. a) oder Widerrufsgründe nach Art. 63 AuG vorliegen (lit. b). Einen derartigen Widerrufsgrund setzt eine ausländische Person unter anderem dann, wenn sie "zu einer längerfristigen Freiheitsstrafe verurteilt wurde" (Art. 62 lit. b AuG in Verbindung mit Art. 63 lit. a AuG). Als längerfristig im Sinne von Art. 62 lit. b AuG gilt eine Freiheitsstrafe, wenn ihre Dauer ein Jahr überschreitet (BGE 135 II 377 E. 4.2 und E. 4.5 S. 379 ff.). Wird diese Grenze erreicht, spielt es keine Rolle, ob die Freiheitsstrafe bedingt, teilbedingt oder unbedingt ausgesprochen wurde. Verlangt wird aber, dass sich das genannte Strafmass aus einem einzigen Strafurteil ergibt und nicht bloss durch Zusammenrechnung von kürzeren Freiheitsstrafen aus einer Mehrzahl von Erkenntnissen erreicht wird (BGE 137 II 297 E. 2 S. 299 ff.; Urteil 2C_828/2011 vom 12. Oktober 2012 E. 2.1 [zur Publikation vorgesehen]). Bei gegebenen Voraussetzungen rechtfertigt sich der Widerruf bzw. die Verweigerung der Verlängerung der Bewilligung zudem nur, wenn die jeweils im Einzelfall vorzunehmende Interessenabwägung die entsprechende Massnahme als verhältnismässig erscheinen lässt, wobei namentlich die Schwere des Verschuldens, die Dauer der Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen sind (vgl. Art. 96 AuG; Urteil 2C_817/2012 vom 19. Februar 2013, E. 2.1.2 mit Hinweisen). Was das Fernhalteinteresse anbetrifft, so darf bei Ausländern, welche sich nicht auf das Freizügigkeitsabkommen (FZA; SR 0.142.112.681) berufen können, im Rahmen der Interessenabwägung abgesehen von der aktuellen Gefährdung der öffentlichen Ordnung und Sicherheit, die von der betroffenen Einzelperson ausgeht, namentlich auch generalpräventiven Gesichtspunkten Rechnung getragen werden (Urteile 2C_282/2012 vom 31. Juli 2012 E. 2.5 mit Hinweis; 2C_679/2011 vom 21. Februar 2012 E. 3. 1).
3.2 Hat ein Ausländer nahe Verwandte mit einem gefestigten Anwesenheitsrecht in der Schweiz und wird die intakte familiäre Beziehung tatsächlich gelebt, kann es Art. 8 EMRK bzw. Art. 13 Abs. 1 BV verletzen, wenn ihm die Anwesenheit in der Schweiz untersagt und damit sein Familienleben vereitelt wird (BGE 130 II 281 E. 3.1 S. 285 mit Hinweisen). Der betreffende Anspruch gilt indessen nicht absolut. Vielmehr ist nach Art. 8 Ziff. 2 EMRK ein Eingriff in das durch Ziff. 1 geschützte Rechtsgut statthaft, soweit er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ruhe und Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung und zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesellschaft und Moral sowie der Rechte und Freiheiten anderer notwendig ist. Die Konvention verlangt insofern eine Abwägung der sich gegenüberstehenden privaten Interessen an der Bewilligungserteilung und den öffentlichen Interessen an deren Verweigerung, wobei letztere in dem Sinne überwiegen müssen, dass sich der Eingriff als notwendig erweist (BGE 135 I 143 E. 2.1 S. 147, 153 E. 2.2.1 S. 156; 122 II 1 E. 2 S. 6 mit Hinweisen). Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind die Schwere des begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die betroffene Person sowie deren familiäre Situation zu berücksichtigen. Zudem sind die Dauer der ehelichen Beziehung und weitere Gesichtspunkte relevant, welche Rückschlüsse auf deren Intensität zulassen (Geburt und Alter der Kinder; Kenntnis der Tatsache, dass die Beziehung wegen der Straftat unter Umständen nicht in der Schweiz gelebt werden kann). Von Bedeutung sind auch die Nachteile, welche dem Ehepartner oder den Kindern erwachsen würden, müssten sie dem Betroffenen in dessen Heimatstaat folgen (Urteile 2C_793/2008 vom 27. März 2009, E. 2.1; 2A.65/2006 vom 23. Juni 2006, E. 2 mit Hinweis auf das Urteil des Europäischen Gerichtshofes für Menschenrechte vom 2. August 2001 i.S. Boultif gegen die Schweiz vom 2. August 2001 [Nr. 54273/00] § 46 ff.; vgl. auch das Urteil des EGMR Üner gegen die Niederlande vom 18. Oktober 2006 [Nr. 46410/99], N. 57, sowie Maslov gegen Österreich vom 23. Juni 2008 [Nr. 1638/03] N. 77 ff.).
4. Mit der Verurteilung des Beschwerdeführers 1 zu einer Freiheitsstrafe von 3 Jahren ist vorliegend der Widerrufsgrund von Art. 62 lit. b AuG gegeben. Die Beschwerdeführenden bestreiten dies nicht. Strittig bleibt jedoch die behauptete Verletzung des Verhältnismässigkeitsgrundsatzes bzw. die Abwägung der auf dem Spiel stehenden privaten und öffentlichen Interessen.
4.1 Die Beschwerdeführenden bringen vor, die Tochter wende sich mittlerweile gegen die Nichtverlängerung der Aufenthaltsbewilligung ihres Vaters. Wenn schon das Opfer seiner Straftaten den weiteren Zusammenhalt der Familie wünsche, so relativiere dies das öffentliche Interesse an einer dauerhaften Fernhaltung des Beschwerdeführers 1 sehr stark. Er selbst werde in seiner Heimat als Angehöriger der tamilischen Minderheit benachteiligt. Der Beschwerdeführerin 2 und den minderjährigen Kindern sei eine Ausreise nach Sri Lanka nicht zuzumuten. Diese privaten Interessen wie auch ein geringes Rückfallrisiko seitens des Beschwerdeführers 1 seien von der Vorinstanz ungenügend berücksichtigt worden.
4.2 Entgegen den Vorbringen der Beschwerdeführenden hat die Vorinstanz die auf dem Spiel stehenden Interessen im Rahmen von Art. 62 lit. b AuG bzw. Art. 8 Ziff. 2 EMRK in zulässiger Weise gegeneinander abgewogen:
4.2.1 Ausgangspunkt und Massstab für die Schwere des Verschuldens und die fremdenpolizeiliche Interessenabwägung im Rahmen eines Bewilligungsentzugs gestützt auf Art. 62 lit. b AuG (Verurteilung zu einer längerfristigen Freiheitsstrafe) ist die vom Strafgericht verhängte Strafe (BGE 129 II 215 E. 3.1 S. 216). Die Vorinstanz ist aufgrund der mehrjährigen Freiheitsstrafe zurecht von einem schweren Verschulden des Beschwerdeführers 1 ausgegangen. Dieser war wegen Tätlichkeit, Drohung, mehrfacher sexueller Handlungen mit Kindern, mehrfachen Versuchs der sexuellen Handlungen mit Kindern, mehrfacher Pornografie, Pornografie gemäss Art. 197 Ziff. 3 bis StGB, mehrfachen Inzests sowie wegen mehrfachen Versuchs des Inzests zu einer Freiheitsstrafe von drei Jahren verurteilt worden. Im Rahmen dieser Delinquenz hatte der Beschwerdeführer 1 seine Tochter während rund vier Jahren missbraucht; nach den Erwägungen des Strafgerichts nützte er seine Rolle als Erziehungsberechtigter auf eine schamlose Art aus, sodass seine Tochter in ihrer Entwicklung nachhaltigen Schaden nahm. Der Beschwerdeführer 1 delinquierte vor dieser Tat und auch danach; er befand sich wegen vorhergehender Verurteilungen teils noch in der Probezeit. Das Strafgericht sprach von einem schweren Verschulden und attestierte dem Beschwerdeführer 1 eine überwiegende Uneinsichtigkeit.
4.2.2 Soweit die Beschwerdeführenden hiergegen - wenn überhaupt rechtsgenüglich - vorbringen, dem Beschwerdeführer 1 sei vom behandelnden Psychiater keine sexuelle Deviation attestiert worden, sodass von einem geringen Rückfallrisiko und einem entsprechend geringen öffentlichen Interesse an seiner Fernhaltung auszugehen sei, kann ihnen nicht gefolgt werden.
Der Beschwerdeführer 1 bestreitet nach wie vor, seine Tochter missbraucht zu haben. Er war gemäss den vorinstanzlichen Feststellungen im Rahmen seiner psychiatrischen Behandlung lediglich bereit, sich allgemein mit der Thematik sexueller Übergriffe zu befassen, nicht jedoch mit seiner eigenen Tat. Es ist daher - wie die Vorinstanz zurecht ausführt - nicht nachvollziehbar, wenn der Beschwerdeführer 1 vorbringt, eine Rückfallwahrscheinlichkeit sei "praktisch ausgeschlossen". Im Übrigen müsste bei Drittstaatsangehörigen für das Fernhalteinteresse ohnehin nicht allein auf die Rückfallwahrscheinlichkeit abgestellt werden: Das Bundesgericht verfolgt bei Delikten gegen die körperliche und sexuelle Integrität eine strenge Praxis (BGE 125 II 521 E. 4.a/aa S. 526 f.; 122 II 433 E. 2.c S. 436 f.; Urteile 2C_481/2012 vom 1. März 2013 E.3.3; 2C_371/2012 vom 20. Dezember 2012 E. 3.2). Selbst ein relativ geringes Rückfallrisiko müsste bei den durch den Beschwerdeführer 1 begangenen Delikten (Verurteilungen gestützt auf Art. 197 Ziff. 1 und 3bis, Art. 213 StGB) nicht hingenommen werden. Die Vorinstanz durfte - auch unter Berücksichtigung von generalpräventiven Gesichtspunkten (vgl. Urteile 2C_282/2012 vom 31. Juli 2012 E. 2.5; 2C_13/2011 vom 22. März 2011 E. 2.2; 2C_28/2010 vom 25. März 2011 E. 2.3; 2C_466/2009 vom 13. Januar 2010 E. 5.2; 2C_36/2009 vom 20. Oktober 2009 E. 2.1) - davon ausgehen, dass ein wesentliches öffentliches Interesse besteht, seine Anwesenheit zu beenden.
4.2.3 Die gegenläufigen privaten Interessen des Beschwerdeführers 1 am Verbleib in der Schweiz fallen demgegenüber - wie die Vorinstanz zu Recht ausgeführt hat - weniger ins Gewicht. Gegen seine Ausweisung spricht zwar der Umstand, dass er seit mehr als 20 Jahren in der Schweiz ist, jedoch liegt trotz der langen Aufenthaltsdauer aufgrund der schweren und wiederholten Straffälligkeit (sowie der Verschuldung) keine gelungene Integration vor. Der Beschwerdeführer 1 bringt zwar vor, er werde als Angehöriger der tamilischen Minderheit nach dem Bürgerkrieg "nach wie vor benachteiligt", substanziiert jedoch nicht, inwiefern ihm eine Rückkehr nach Sri Lanka und in die dortigen Verhältnisse mit Bezug auf seine konkrete Situation tatsächlich unzumutbar wäre (vgl. Urteil 2C_695/2012 vom 28. Januar 2013 E. 3.2.3). Er hat seine Kindheit und Jugend in Sri Lanka verbracht und ist demnach mit den sozio-kulturellen Gegebenheiten wie auch mit der Sprache seiner Heimat vertraut. Er kehrte gemäss den vorinstanzlichen Feststellungen auch unlängst dorthin zurück, sodass ihm eine (Re-)Integration zumutbar sein wird. Dass die wirtschaftlichen Verhältnisse in seinem Herkunftsland wie von ihm vorgebracht schwierig sind, kann im Rahmen der Überprüfung der Nichtverlängerung der Aufenthaltsbewilligung nicht entscheidend sein (vgl. Urteile 2C_695/2012 vom 28. Januar 2013 E. 3.2.3; 2C_1029/2011 vom 10. April 2012 E. 3.3.2 mit Hinweisen).
4.2.4 Zu prüfen bleiben die Auswirkungen des angefochtenen Entscheids auf die familiären Beziehungen. Zwar fallen die Beziehungen des Beschwerdeführers 1 zu seiner Ehefrau und seinen minderjährigen Kindern zweifellos in den Schutzbereich von Art. 8 EMRK (vgl. E. 3.2). Die Beschwerdeführerin 2 hatte ihren Gatten in Sri Lanka geheiratet und sich danach mit ihm in der Schweiz niedergelassen. Ihr musste in der Folge klar werden, dass sie die Beziehung angesichts der wiederholten Verurteilungen ihres Ehegatten allenfalls inskünftig nicht weiter zusammen mit ihm in der Schweiz würde leben können. Die gemeinsamen minderjährigen Kinder teilen in der Regel den Aufenthaltsort ihrer Eltern oder des für sie verantwortlichen Elternteils. Sie sind mittlerweile gut sieben bzw. knapp drei Jahre alt und befinden sich noch in einem anpassungsfähigen Alter (vgl. Urteil 2C_656/2012 vom 8. Mai 2012 E. 3.2), sodass es ihnen zumutbar wäre, allenfalls gemeinsam mit den Eltern in das Heimatland des Vaters zurückzukehren (vgl. BGE 127 II 60 E. 2a S. 67; 122 II 289 E. 3c S. 298). Der Beschwerdeführerin 2 steht es aber auch frei, mit den Kindern in der Schweiz zu verbleiben und den Kontakt mit dem Beschwerdeführer im Rahmen von Besuchen, Mitteln der Telekommunikation und Briefen aufrecht zu erhalten (Urteil 2C_679/2011 vom 21. Februar 2012 E. 3.4.3).
4.3 Soweit sich die Beschwerdeführenden zusätzlich auf Art. 5 Abs. 2 BV berufen, kann auf die vorstehenden Erwägungen betreffend Verhältnismässigkeitsprüfung verwiesen werden (vgl. BGE 135 V 172 E. 7.3.2 S. 182; 131 I 91 E. 3.3 S. 99; Urteil 2C_1029/2011 vom 10. April 2012 E. 3.3.4). Eine Verletzung der weiteren angerufenen Grundrechte wird nicht rechtsgenüglich dargetan, sodass auf diese Rügen nicht eingegangen werden kann (vgl. oben E. 1.3).
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Infolge Aussichtslosigkeit der Beschwerde (wiederholte Delinquenz, darunter Verurteilung zu einer dreijährigen Freiheitsstrafe aufgrund von Delikten gegen die sexuelle Integrität) kann dem Gesuch der Beschwerdeführenden um unentgeltliche Rechtspflege auch im bundesgerichtlichen Verfahren nicht entsprochen werden. Dem Verfahrensausgang entsprechend haben sie die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 66 BGG). Es sind keine Parteientschädigungen geschuldet (Art. 68 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. 2.1 Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
2.2 Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführenden auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Graubünden, 1. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 28. März 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni