Sachverhalt:
A. B._ (geb. 1978), mazedonische Staatsangehörige, reiste am 9. Januar 1994 im Rahmen des Familiennachzugs zu ihren Eltern in die Schweiz ein und erhielt eine Aufenthaltsbewilligung. Im Jahr 1999 heiratete sie den ebenfalls aus Mazedonien stammenden A._ (geb. 1978). Dieser reiste am 27. Dezember 1999 in die Schweiz ein und erhielt eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Am 25. Oktober 2001 wurde der Sohn C._, am 26. Mai 2008 die Tochter D._ geboren.
Am 26. November 2004 sprach das Ausländeramt des Kantons Thurgau (heute: Migrationsamt Thurgau; nachfolgend: Migrationsamt) gegenüber A._ eine Verwarnung aus und drohte ihm die Wegweisung an mit der Begründung, er sei mit sechs Betreibungen über Fr. 38'807.50 und drei Verlustscheinen über Fr. 34'358.30 verzeichnet. Am 12. April 2006 verwarnte das Migrationsamt A._ erneut: Er sei am 20. Juni 2005 wegen Missbrauchs von Ausweisen und der Nichtabgabe entzogener Kontrollschilder trotz behördlicher Aufforderung mit Fr. 300.-- gebüsst worden. Zudem sei er am 13. Januar 2006 wegen grober Verkehrsregelverletzung mit Fr. 1'100.-- gebüsst worden. Die (schlechte) finanzielle Lage sei seit der ersten Verwarnung relativ stabil geblieben.
Am 17. Oktober 2007 gründeten A._ und B._ die G._ GmbH, wobei A._ mit Einzelunterschrift, B._ hingegen nicht zeichnungsberechtigt war. Der am 29. Oktober 2010 über die Gesellschaft verhängte Konkurs wurde am 3. Februar 2011 mangels Aktiven eingestellt.
B. Am 29. November 2010 teilte das Migrationsamt A._ und B._ mit, es prüfe die Nichtverlängerung der am 8. Januar 2011 auslaufenden Aufenthaltsbewilligungen, die Wegweisung aus der Schweiz sowie einen Antrag an das Bundesamt für Migration auf Anordnung eines Einreiseverbots, und gewährte ihnen das rechtliche Gehör. A._ und B._ liessen sich mit Stellungnahme vom 7. Januar 2011 vernehmen und beantragten gleichentags die Verlängerung der Aufenthaltsbewilligung bzw. die Erteilung der Niederlassungsbewilligung.
Am 18. Februar 2011 wies das Migrationsamt die Gesuche um Verlängerung der Aufenthaltsbewilligung und um Erteilung der Niederlassungsbewilligung ab und wies A._ und B._ sowie deren Kinder C._ und D._ weg. Den dagegen erhobenen Rekurs wies das Departement für Justiz und Sicherheit des Kantons Thurgau (nachfolgend: Justiz- und Sicherheitsdepartement) am 7. Juni 2011 ab. Das Verwaltungsgericht des Kantons Thurgau bestätigte diesen Entscheid auf Beschwerde hin mit Urteil vom 31. August 2011.
C. A._ und B._ sowie ihre Kinder C._ und D._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Rechtsbegehren, der angefochtene Entscheid sei aufzuheben und die Vorinstanz bzw. der Beschwerdegegner sei anzuweisen, ihnen den weiteren Aufenthalt im Kanton Thurgau zu verlängern.
Das Migrationsamt und das Justiz- und Sicherheitsdepartement verzichten auf eine Stellungnahme und beantragen die Abweisung der Beschwerde, ebenso das Verwaltungsgericht des Kantons Thurgau. Das Bundesamt für Migration beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei diese abzuweisen. A._ und B._ sowie ihre Kinder C._ und D._ lassen sich mit Replik vom 10. Februar 2012 vernehmen.
D. Am 3. November 2011 hat der Abteilungspräsident der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.
Erwägungen:
1. Angefochten ist ein letztinstanzlicher kantonaler Entscheid auf dem Gebiet des Ausländerrechts, welcher grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (Art. 82 lit. a BGG und Art. 90 BGG). Gemäss Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde unzulässig gegen Entscheide betreffend ausländerrechtliche Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. In Bezug auf die Niederlassungsbewilligung, deren Erteilung von den Vorinstanzen verweigert wurde, ist diese Voraussetzung vorliegend nicht erfüllt (vgl. Art. 34 Abs. 2 AuG; SR 142.20). Die Beschwerdeführenden beantragen vor Bundesgericht denn auch lediglich, ihnen sei "der weitere Aufenthalt im Kanton Thurgau", mithin die Aufenthaltsbewilligung zu verlängern. Sie berufen sich dabei auf Art. 8 Ziff. 1 EMRK (Recht auf Achtung des Privatlebens). Mit Blick auf die lange Anwesenheitsdauer - insbesondere der Beschwerdeführerin 2 - in der Schweiz ist dieser Anspruch nicht von vornherein ausgeschlossen (vgl. Urteil des EGMR Gezginci gegen Schweiz vom 9. Dezember 2010 § 56 f., in: Plädoyer 2011 1 S. 65). Das Bundesgericht hat es jedoch bisher abgelehnt, ausgehend von einer bestimmten Aufenthaltsdauer schematisierend eine besondere, einen Anspruch auf die Erteilung eines Anwesenheitsrechts begründende Verwurzelung in den hiesigen Verhältnissen anzunehmen (BGE 130 II 281 E. 3.2.1 S. 286 mit Hinweis auf Urteil 2A.471/2001 vom 29. Januar 2002 E. 2b/ee). Bei der Frage, ob der bisherige Aufenthalt in der Schweiz in den Schutzbereich des Privatlebens im Sinn von Art. 8 Ziff. 1 EMRK fällt, sind zusätzlich qualitative Kriterien der Integration zu berücksichtigen. Demgemäss bedarf es hierfür besonders intensiver, über eine normale Integration hinausgehender privater Bindungen gesellschaftlicher oder beruflicher Natur bzw. entsprechender vertiefter sozialer Beziehungen zum ausserfamiliären bzw. ausserhäuslichen Bereich (BGE 130 II 281 E. 3.2.1 S. 286 mit Hinweis auf BGE 126 II 425 E. 4c/aa S. 432). Eine solche Verwurzelung ist vorliegend aufgrund der langjährigen Anwesenheitsdauer insbesondere der Beschwerdeführerin 2 und ihrer Eltern sowie der schulischen Situation des Sohnes (im Zeitpunkt des angefochtenen Urteils Eintritt ins vierte Schuljahr) gegeben. Damit liegt ein gefestigtes Anwesenheitsrecht vor, welches einen grundsätzlichen Anspruch auf den weiteren Verbleib in der Schweiz vermittelt. Ob der Anspruch auf Verlängerung der Bewilligung im konkreten Fall zu bejahen ist, betrifft nicht die Eintretensfrage, sondern die materielle Behandlung der Beschwerde (BGE 136 II 177 E. 1.1 S. 179). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist somit zulässig.
2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht (inklusive Bundesverfassungsrecht) und Völkerrecht gerügt werden (Art. 95 lit. a und b BGG). Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur beanstandet bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von Art. 95 BGG beruht (Art. 97 Abs. 1 BGG bzw. Art. 105 Abs. 2 BGG). Die Rüge, der Sachverhalt sei offensichtlich unrichtig festgestellt worden, ist gleichzusetzen mit der Willkürrüge (BGE 137 I 58 E. 4.1.2 S. 62; 133 II 249 E. 1.2.2 S. 252). Diese Rüge, welche rechtsgenüglich substanziiert vorzubringen ist (Art. 42 Abs. 2 BGG; vgl. BGE 133 II 249 E. 1.4.3 S. 254), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG).
Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Im Fall einer unvollständigen Sachverhaltsfeststellung, welche ebenfalls als Rechtsverletzung im Sinn von Art. 95 lit. a BGG zu behandeln ist, kann das Bundesgericht gemäss Art. 107 Abs. 2 BGG die Sache an die Vorinstanz oder eine untere Instanz zur ergänzenden Abklärung der Umstände zurückweisen (Urteil 2C_273/ 2010 vom 6. Oktober 2010 E. 1.3 mit Hinweis).
3. Im angefochtenen Urteil wird die Nichtverlängerung der Aufenthaltsbewilligungen der Beschwerdeführenden bestätigt. Gemäss Art. 33 Abs. 3 AuG ist die Aufenthaltsbewilligung befristet und kann verlängert werden, wenn keine Widerrufsgründe nach Art. 62 AuG vorliegen. Art. 62 lit. c AuG erlaubt den Widerruf der Bewilligung, wenn die ausländische Person erheblich oder wiederholt gegen die öffentliche Sicherheit und Ordnung in der Schweiz oder im Ausland verstossen hat oder diese gefährdet oder die innere oder die äussere Sicherheit gefährdet. Art. 80 Abs. 1 VZAE enthält eine nicht abschliessende Aufzählung von Handlungen, die einen Verstoss gegen die öffentliche Sicherheit und Ordnung darstellen. Dies ist der Fall bei einer Missachtung von gesetzlichen Vorschriften und behördlichen Verfügungen (Art. 80 Abs. 1 lit. a VZAE) und bei mutwilliger Nichterfüllung der öffentlich-rechtlichen oder privatrechtlichen Verpflichtungen (Art. 80 Abs. 1 lit. b VZAE). Ob der Widerrufsgrund des Art. 62 lit. c AuG (in der ersten Variante, ohne die Variante "Gefährdung der inneren oder äusseren Sicherheit") vorliegt, ist in Bezug auf den Beschwerdeführer 1 und die Beschwerdeführerin 2 getrennt zu prüfen.
4. 4.1 Hinsichtlich des Beschwerdeführers 1 kommt die Vorinstanz zum Schluss, die von ihm begangenen Delikte würden für sich allein nicht ausreichen, um einen Widerruf der Aufenthaltsbewilligung zu begründen, da es diesbezüglich an der notwendigen Erheblichkeit fehle. Allerdings würden diese Delikte dadurch an Erheblichkeit gewinnen, dass der Beschwerdeführer 1 trotz zweier Verwarnungen erneut und mehrfach straffällig geworden sei. Im Rahmen der Gesamtbeurteilung sei dieses Verhalten zu Lasten des Beschwerdeführers 1 zu berücksichtigen.
In Bezug auf die finanzielle Situation seien die Voraussetzungen für den Widerruf der Aufenthaltsbewilligung erfüllt. Im Zeitpunkt der zweiten Verwarnung vom 12. April 2006 hätten gegen den Beschwerdeführer 1 sieben Betreibungen über total Fr. 39'295.40 sowie fünf Verlustscheine über total Fr. 35'594.45 vorgelegen. Der Beschwerdeführer 1 habe offenbar keine ernsthaften Bemühungen unternommen, seine Schulden zu sanieren. So hätten im Zeitpunkt der Gewährung des rechtlichen Gehörs am 29. November 2010 gegen den Beschwerdeführer 1 14 Betreibungen über total 24'628.30 sowie neun Verlustscheine über total Fr. 42'514.50 vorgelegen. Zwar werde damit der Betrag von Fr. 75'000.--, welcher nach der Praxis der Ostschweizer Fremdenpolizeichefs grundsätzlich eine Nichtverlängerung der Aufenthaltsbewilligung rechtfertige, nicht erreicht. Doch sei zu Lasten des Beschwerdeführers 1 und der Beschwerdeführerin 2 zu berücksichtigen, dass sie eine GmbH gegründet und in den Konkurs gewirtschaftet hätten. In diesem Zusammenhang sei dem Beschwerdeführer 1 und der Beschwerdeführerin 2 mutwilliges Handeln vorzuwerfen, denn anstatt bestehende Schulden abzubauen, hätten sie in erheblichem Ausmass neue Schulden angehäuft. Erschwerend komme hinzu, dass sie für die Gründung der GmbH nicht einmal die Bewilligung für selbständige Erwerbstätigkeit eingeholt bzw. abgewartet hätten. Am 7. Oktober 2010 hätten gegen die G._ GmbH 18 Betreibungen über total Fr. 68'393.14 sowie neun Verlustscheine über total Fr. 42'303.30 bestanden. Aus den Akten gehe nicht hervor, dass der Beschwerdeführer 1 und die Beschwerdeführerin 2 vor Androhung der Nichtverlängerung der Aufenthaltsbewilligung ernsthaft um Schuldentilgung bemüht gewesen wären. Insgesamt sei davon auszugehen, dass sich die finanzielle Situation des Beschwerdeführers 1 und der Beschwerdeführerin 2 auch nach Androhung der Wegweisung im Ergebnis nicht gebessert habe, da lediglich alte Schulden bezahlt und neue eingegangen worden seien. Die beiden Verwarnungen hätten ihre Wirkung offenkundig verfehlt.
4.2 Hinsichtlich der Beschwerdeführerin 2 erwägt die Vorinstanz, zwar hätten sich die Schulden im Wesentlichen beim Beschwerdeführer 1 angehäuft, doch würden die vorstehenden Ausführungen grundsätzlich auch auf die Beschwerdeführerin 2 zutreffen. So habe sie von den Schulden des Beschwerdeführers 1, der im Wesentlichen allein für den Familienunterhalt aufgekommen sei, profitiert. Selbst habe sie keine ernsthaften Anstrengungen unternommen, um finanziell zum Familienunterhalt beizutragen und die Schuldensituation zu entschärfen. Zudem sei sie an der G._ GmbH beteiligt gewesen und damit für die mutwillig vereitelte Sanierung der bestehenden Schulden mitverantwortlich. Darüber hinaus drohe der Beschwerdeführerin 2 bei einem alleinigen Verbleib in der Schweiz die Fürsorgeabhängigkeit. Deshalb sei der Wegweisungsgrund von Art. 62 lit. c AuG in Verbindung mit Art. 80 Abs. 1 lit. b VZAE auch in Bezug auf die Beschwerdeführerin 2 erfüllt.
4.3 Die Nichtverlängerung der Aufenthaltsbewilligung sei sowohl in Bezug auf den Beschwerdeführer 1 als auch die Beschwerdeführerin 2 verhältnismässig. Beide hätten ihre prägende Schulzeit in Mazedonien verbracht. Sie seien ohne besondere berufliche Ausbildung in die Schweiz gekommen, hätten sich nicht nachhaltig in die hiesige Arbeitswelt integrieren können und seien oft in Beschäftigungsprogrammen tätig bzw. arbeitslos gewesen. Trotz des relativ langen Aufenthalts in der Schweiz sei keine besondere soziale Verwurzelung erkennbar. Den noch nicht zwölfjährigen Kindern könne die Übersiedlung in ihre Heimat zugemutet werden. Die öffentlichen Interessen an der Wegweisung der Beschwerdeführenden würden daher deren private Interessen überwiegen.
5. Die Vorinstanz begründet ihre Auffassung, die Voraussetzungen für die Nichtverlängerung der Aufenthaltsbewilligung seien erfüllt, in erster Linie mit der Höhe der im Jahr 2010 vorliegenden Betreibungen. Sie stellt bei der Beurteilung der finanziellen Situation des Beschwerdeführers 1 auf den Zeitpunkt der Gewährung des rechtlichen Gehörs am 29. November 2010 ab und kommt zum Schluss, es sei davon auszugehen, dass sich die Verhältnisse seither im Ergebnis nicht geändert hätten.
5.1 Nachdem das Justiz- und Sicherheitsdepartement den Entscheid des Migrationsamtes bzw. dessen Begründung vollumfänglich geschützt hatte, legten die Beschwerdeführenden der Vorinstanz als Belege für ihre finanzielle Situation u.a. einen Betreibungsregisterauszug vom 20. Juni 2011, eine Zahlungsvereinbarung mit der Intrum Justitia vom 4. Mai 2011, eine Erklärung der Arbeitgeberin des Beschwerdeführers 1 vom 20. Juni 2011, einen Arbeitsvertrag vom 26. Februar 2011 sowie ein Schreiben der I._ AG vom 21. Juni 2011 betreffend die Auszahlung eines Guthabens an den Beschwerdeführer 1 vor.
Die Vorinstanz würdigt die eingereichten Unterlagen folgendermassen: Mit dem ins Recht gelegten Betreibungsregisterauszug vom 20. Juni 2011 werde nicht aufgezeigt, dass die dort ausgewiesene Bezahlung von Schulden bereits vor November 2010 erfolgt sei. Auch die Zahlungsvereinbarung der Intrum Justitia datiere erst vom 4. Mai 2011 und damit "weit nach der Wegweisungsverfügung vom 18. Februar 2011". Zudem sei unglaubwürdig, dass die ursprünglich als Darlehen konzipierte Zahlung der Arbeitgeberin des Beschwerdeführers 1 in eine Schenkung umgewandelt worden sein solle; vielmehr habe eine Umschichtung der Schulden stattgefunden.
5.2 Die Beschwerdeführenden machen geltend, die Vorinstanz habe den Sachverhalt unvollständig festgestellt, indem sie die aktuellen Verhältnisse im Entscheidzeitpunkt nicht berücksichtigt habe. Die Beschwerdeführenden hätten bis dahin einen enormen Schuldenabbau erreicht. Der Betreibungsauszug sei inzwischen blank und es habe eine Zahlungsvereinbarung mit der Intrum Justitia getroffen werden können. Von dem empfangenen Darlehen seiner Arbeitgeberin habe der Beschwerdeführer 1 Fr. 15'000.-- zurückvergüten können. Die aufgrund der Geschäftsentwicklung zu erwartenden Boni würden die vollständige Tilgung des Darlehens erlauben. Zum Beweis legen die Beschwerdeführenden Lohnabrechnungen von November 2010 bis September 2011, zwei Bankauszüge der Arbeitgeberin des Beschwerdeführers 1 von September 2011 und eine Stellungnahme der Arbeitgeberin des Beschwerdeführers 1 vom 13. Oktober 2011 betreffend Darlehensgewährung bzw. Schuldensanierung samt Bankauszügen vor.
5.3 Die Vorinstanz hat erkennen lassen, dass sie die Schuldentilgungen nur bis November 2010, auf keinen Fall aber nach dem Erlass der Verfügung vom 18. Februar 2011 berücksichtigt hat. Die vor Bundesgericht eingereichten neuen Beweismittel sind als zulässige Noven entgegenzunehmen, weil die Beschwerdeführenden damit ihren Standpunkt untermauern, wonach die Schulden bis zum Zeitpunkt des angefochtenen Urteils erheblich abgetragen worden seien und diesem Umstand im angefochtenen Urteil nicht Rechnung getragen worden sei (zur Zulässigkeit unechter Noven vgl. etwa Urteil 8C_184/2009 vom 25. August 2009 E. 4.3.1; ferner ULRICH MEYER/JOHANNA DORMANN, in: Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 41 zu Art. 99 BGG).
Bei der Prüfung der materiellen Rechtmässigkeit eines fremdenpolizeirechtlichen Entscheids sind für das Bundesgericht in der Regel die tatsächlichen Verhältnisse massgebend, wie sie im Zeitpunkt des Entscheids der richterlichen Vorinstanz herrschten (BGE 127 II 60 E. 1b S. 63). Die Vorinstanz ihrerseits wäre verpflichtet gewesen, die von den Beschwerdeführenden behaupteten Anstrengungen zur Schuldentilgung bis zum Entscheidzeitpunkt zu berücksichtigen und gestützt darauf die Schuldensituation abzuklären (vgl. BGE 135 II 369 E. 3.3). Die Vorinstanz hat jedoch die ihr vorgelegten Beweismittel zur Schuldensanierung bis zum Entscheidzeitpunkt nur unzureichend gewürdigt, so dass die sich darauf stützende Sachverhaltserhebung als unvollständig gelten muss. Als Folge davon ist eine vertiefte Auseinandersetzung mit der Frage der Mutwilligkeit des Schuldenmachens unterblieben. Das angefochtene Urteil basiert auf einem unvollständigen Sachverhalt, was einer offensichtlich unrichtigen, d.h. willkürlichen Sachverhaltsfeststellung gleichkommt, und entbehrt bezüglich der Mutwilligkeit der Schuldenwirtschaft einer sachbezogenen Begründung. Dies führt zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Urteils.
Weil der Sachverhalt nur unvollständig erhoben worden ist, kann das Bundesgericht kein reformatorisches Urteil fällen, so dass die Sache in Anwendung von Art. 107 Abs. 2 BGG zur ergänzenden Ermittlung der Umstände, insbesondere der Schuldensituation im Entscheidzeitpunkt, an die Vorinstanz zurückzuweisen ist. Infolge der Aufhebung des angefochtenen Urteils vom 31. August 2011 sind die rechtserheblichen Tatsachen, allenfalls nach erneuter Instruktion, bis zum neuen Entscheid der Vorinstanz zu berücksichtigen.
5.4 Ob die Voraussetzungen für die Nichtverlängerung der Aufenthaltsbewilligung erfüllt sind, ist für den Beschwerdeführer 1 und die Beschwerdeführerin 2 sowie deren Kinder getrennt zu prüfen.
Bei der Frage, welchen Anteil die Beschwerdeführerin 2 an der Schuldensituation hat, wird zu berücksichtigen sein, dass die Beschwerdeführerin als Gesellschafterin der G._ GmbH nicht zeichnungsberechtigt war und dass gegen sie - soweit aktenkundig - keine Betreibungen vorliegen. Im Gegensatz zum Beschwerdeführer 1 hat die Beschwerdeführerin 2 keine Straftaten begangen; dementsprechend ist sie nie verwarnt worden. Schliesslich kann ihr die Verlängerung der Aufenthaltsbewilligung auch nicht mit der Begründung verweigert werden, ihr drohe bei einem alleinigen Verbleib in der Schweiz die Sozialhilfeabhängigkeit, ohne dass diesbezüglich Instruktionen stattgefunden hätten. Nach der Rechtsprechung ist für die Bejahung dieses Widerrufsgrundes eine konkrete Gefahr der Sozialhilfeabhängigkeit erforderlich und es kann dafür nicht auf Hypothesen und pauschalierte Gründe abgestellt werden (vgl. Urteil 2C_685/2010 vom 30. Mai 2011 E. 2.3.1 und E. 2.3.2). Zu beachten ist ferner, dass Sozialversicherungsleistungen keine Sozialhilfe darstellen (BGE 135 II 265 E. 3.7 S. 272 mit Hinweis), weshalb deren Bezug vom Tatbestand des Art. 62 lit. e AuG nicht erfasst wird.
Im Hinblick auf die Kinder des Beschwerdeführers 1 und der Beschwerdeführerin 2 ist darauf hinzuweisen, das sie keinen Widerrufsgrund gesetzt haben. Ihr Anspruch auf Verlängerung der (abgeleiteten) Aufenthaltsbewilligung entfällt, wenn beiden Eltern die Aufenthaltsbewilligung nicht verlängert werden sollte.
6. Die Beschwerde erweist sich hinsichtlich der Rüge der unvollständigen Sachverhaltsfeststellung sowie der Gehörsverletzung als begründet und ist daher gutzuheissen. Das angefochtene Urteil ist aufzuheben und die Sache in Anwendung von Art. 107 Abs. 2 BGG zu neuer Entscheidung im Sinn der Erwägungen an die Vorinstanz zurückzuweisen.
6.1 Dem Verfahrensausgang entsprechend sind keine Kosten zu auferlegen (vgl. Art. 66 Abs. 1 und 4 BGG).
6.2 Der Kanton Thurgau hat die Beschwerdeführenden für das bundesgerichtliche Verfahren angemessen zu entschädigen (vgl. Art. 68 Abs. 2 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der angefochtene Entscheid wird aufgehoben. Die Sache wird im Sinn der Erwägungen zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Kanton Thurgau hat die Beschwerdeführenden für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Thurgau und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Genner