Sachverhalt:
A. Der aus Serbien stammende A._ (geb. 1978) reiste im Jahre 1993 in die Schweiz ein und wurde in die Niederlassungsbewilligung seines Vaters einbezogen. Eine Berufsausbildung absolvierte er nicht und war zunächst als Hilfsarbeiter tätig. 1998 wurde er u.a. wegen Raufhandels mit einer bedingten Gefängnisstrafe von sechs Wochen und einer Busse von Fr. 800.-- bestraft. Im selben Jahr wurde er erstmals fremdenpolizeilich verwarnt. Am 21. Juli 2000 heiratete er in seiner Heimat die zwei Jahre jüngere Landsfrau B._ und zog sie in die Schweiz nach. Mit ihr, die im Besitz einer Aufenthaltsbewilligung ist, hat er die Zwillingstöchter C._ und D._ (geb. 2003), welche ebenfalls über die Niederlassungsbewilligung verfügen. Am 10. Dezember 2002 war A._ wegen Fahrens in angetrunkenem Zustand und anderen Verkehrsregelverletzungen mit einer bedingten Gefängnisstrafe von 45 Tagen und einer Busse von Fr. 600.-- bestraft und in der Folge ein zweites Mal fremdenpolizeilich verwarnt worden (Androhung der Ausweisung). Bis Februar 2005 war er meistens temporär tätig. Ab März 2005 war er arbeitslos, bezog Leistungen der Arbeitslosenversicherung und nahm zeitweise an verschiedenen Beschäftigungsprogrammen teil. Stellenbewerbungen in dieser Zeit blieben erfolglos.
Am 20. September 2007 wurde A._ vom Bezirksamt Frauenfeld wegen Kaufs und Konsums von insgesamt 8 Gramm Marihuana erneut mit einer Busse von Fr. 50.-- bestraft.
Gegen A._ und seine Ehefrau liegen zahlreiche Betreibungen im Gesamtbetrag von über Fr. 65'000.-- und mehrere Verlustscheine (ca. Fr. 30'000.--) vor. Die Familie bezog ab März 2005 bis zum 8. Juli 2008 Fürsorgegelder von insgesamt Fr. 90'320.55. Seit Mai 2008 arbeitet A._ mit einem Pensum von 100 % als Lagerist bei der Firma R._ AG in Z._. Seine Ehefrau arbeitet auf Abruf im Stundenlohn bei der Firma S._, domiziliert ebenfalls in Z._.
B. Mit Verfügung vom 13. September 2007 verweigerte das Migrationsamt des Kantons Thurgau der ganzen Familie A._ - B._ den weiteren Aufenthalt im Kanton Thurgau und wies die Familie für die Dauer von drei Jahren aus der Schweiz aus, im Wesentlichen mit der Begründung, A._ habe wiederholt zu schweren Klagen Anlass gegeben und sei offensichtlich nicht gewillt, seine bedenkliche wirtschaftliche Situation nachhaltig zu ändern. Es müsse daher angenommen werden, dass er und seine Familie auch in Zukunft der öffentlichen Fürsorge zur Last fallen werde, was die Ausweisung rechtfertige.
Ein gegen diese Verfügung erhobener Rekurs beim Departement für Justiz und Sicherheit des Kantons Thurgau blieb erfolglos, und am 12. November 2008 wies das Verwaltungsgericht des Kantons Thurgau die gegen den Departementsentscheid vom 8. Juli 2008 erhobene Beschwerde ebenfalls ab.
C. Mit gemeinsamer Eingabe vom 19. Januar 2009 führen A._, B._, C._ und D._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, den Entscheid des Verwaltungsgerichts vom 12. November 2008 aufzuheben und das Migrationsamt anzuweisen, der Familie das Aufenthaltsrecht im Kanton Thurgau weiterhin zu gewähren.
Das Migrationsamt beantragt, die Beschwerde abzuweisen. Denselben Antrag stellen das Departement für Justiz und Sicherheit, das Verwaltungsgericht und das Bundesamt für Migration.
Die II. öffentlich-rechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 4. Dezember 2009 an einer öffentlichen Sitzung beraten.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid über eine gestützt auf Art. 10 Abs. 1 lit. a des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG) verfügte Ausweisung, wogegen das ordentliche Rechtsmittel der Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (<ref-law> e contrario). Die Beschwerdeführer sind hierzu legitimiert (<ref-law>).
1.2 Zwar ist am 1. Januar 2008 das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) in Kraft getreten. Praxisgemäss bleibt indessen, in analoger Anwendung von Art. 126 Abs. 1 AuG, das bisherige Recht anwendbar, wenn - wie hier - ein Ausweisungsverfahren noch vor Inkrafttreten des neuen Rechts eröffnet worden ist (vgl. Urteile 2C_745/2008 vom 24. Februar 2009, E. 1.2.2-1.2.4, und 2C_701/2008 vom 26. Februar 2009, E. 2).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG; vgl. <ref-ruling> E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 1.4 S. 287).
1.4 Das Bundesgericht legt sodann seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). 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 <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Das von den Beschwerdeführern als neues Beweismittel eingereichte Zwischenzeugnis der R._ AG vom 8. Dezember 2008 für A._ bleibt als echtes Novum im vorliegenden Verfahren daher unbeachtlich.
2. 2.1 Die Niederlassungsbewilligung erlischt u.a. mit der Ausweisung (Art. 9 Abs. 3 lit. b ANAG), ebenso die Aufenthaltsbewilligung (Art. 9 Abs. 1 lit. d ANAG). Gemäss Art. 10 Abs. 1 lit. a ANAG kann ein Ausländer aus der Schweiz oder aus einem Kanton ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde. Ebenso kann er ausgewiesen werden, wenn sein Verhalten im Allgemeinen und seine Handlungen darauf schliessen lassen, dass er nicht gewillt oder nicht fähig ist, sich in die im Gastland geltende Ordnung einzufügen (Art. 10 Abs. 1 lit. b ANAG). Der Ausländer erfüllt auch dann einen Ausweisungsgrund, wenn er oder eine Person, für die er zu sorgen hat, der öffentlichen Wohltätigkeit fortgesetzt und in erheblichem Mass zur Last fällt (Art. 10 Abs. 1 lit. d ANAG). Fallen mehrere Ausweisungsgründe in Betracht, die je für sich allein genommen die Ausweisung noch nicht zu rechtfertigen vermögen, so ist eine Gesamtbetrachtung vorzunehmen; es ist denkbar, das das Gesamtverhalten des Ausländers zur genannten fremdenpolizeilichen Massnahme Anlass gibt (vgl. Urteile 2C_61/2007 vom 16. August 2007, E. 4, und 2C_329/2009 vom 14. September 2009, E. 4.2.1, je mit Hinweisen).
2.2 Die Ausweisung soll jedoch nur verfügt werden, wenn sie nach den gesamten Umständen angemessen erscheint (Art. 11 Abs. 3 ANAG). Für die Beurteilung der Angemessenheit, d.h. der Verhältnismässigkeit (vgl. <ref-ruling> E. 2a S. 523) der Ausweisung erklärt Art. 16 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer (ANAV) namentlich als wichtig die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz und die ihm und seiner Familie drohenden Nachteile. Da bei der vorzunehmenden Interessenabwägung die persönlichen und familiären Verhältnisse zu berücksichtigen sind, hält eine im Sinne von Art. 11 Abs. 3 ANAG verhältnismässige Ausweisung grundsätzlich auch vor Art. 8 EMRK bzw. <ref-law> (Recht auf Achtung des Privat- und Familienlebens) stand.
3. 3.1 Das Verwaltungsgericht hat erwogen, der Beschwerdeführer 1 sei in der Schweiz mehrfach wegen Verbrechen oder Vergehen gerichtlich bestraft worden und erfülle damit den Ausweisungsgrund von Art. 10 Abs. 1 lit. a ANAG. Die Beschwerdeführer hätten zudem in den letzten Jahren einen beträchtlichen Schuldenberg angehäuft. Selbst die Geburt der beiden Töchter im Juni 2003 habe den Beschwerdeführer 1 nicht dazu bewogen, die finanzielle Verantwortung für seine Familie zu übernehmen; er sei schliesslich ganz arbeitslos und die Familie von der Fürsorge abhängig geworden. Eine günstige Prognose könne nicht gestellt werden: Die berufliche Laufbahn des Beschwerdeführers lasse daran zweifeln, dass er die momentane Festanstellung über längere Zeit behalten werde; vielmehr liege die Vermutung nahe, dass diese Festanstellung hauptsächlich im Hinblick auf das laufende Ausweisungsverfahren zu Stande gekommen sei. Die angeordnete Ausweisung erweise sich auch als verhältnismässig: Beide Elternteile hätten ihre Jugend nicht in der Schweiz verbracht und die Kinder stünden noch im Vorschulalter, weshalb auch für sie die Ausweisung zumutbar sei.
3.2 Die Beschwerdeführer machen geltend, das Urteil vom 4. Februar 1998 (Verurteilung u.a. wegen Raufhandel, vgl. vorne lit. A) sei im Strafregister gelöscht und dürfe dem Ehemann und Vater nicht mehr entgegengehalten werden. Was die - lange zurückliegende - Verurteilung wegen Fahrens in angetrunkenem Zustand betreffe, habe sich der Beschwerdeführer 1 diesbezüglich wohlverhalten und sich nichts mehr zuschulden kommen lassen. Er habe regelmässig temporäre Arbeitseinsätze geleistet und sich immer wieder um eine Anstellung bemüht, was ihm entgegen den Prognosen der Migrationsbehörden dann schliesslich auch mit Erfolg gelungen sei. Seit Mai 2008 sei der Ehemann und Vater als Vollzeitarbeitnehmer beruflich vollständig integriert und erfülle auch seine Pflichten als Versorger. Die Ehefrau verdiene regelmässig mit; und dem Ehepaar gelinge es heute, selbständig und ohne zusätzliche Unterstützung für den Unterhalt ihrer Familie aufzukommen. Aufgrund der aktuellen Verhältnisse sei von einer guten Prognose auszugehen; eine Ausweisung aufgrund der vergangenen Fürsorgeabhängigkeit wäre unverhältnismässig und liege auch nicht im öffentlichen Interesse, was die Rückzahlung der bestehenden Verbindlichkeiten betreffe.
3.2 Die Beschwerdeführer machen geltend, das Urteil vom 4. Februar 1998 (Verurteilung u.a. wegen Raufhandel, vgl. vorne lit. A) sei im Strafregister gelöscht und dürfe dem Ehemann und Vater nicht mehr entgegengehalten werden. Was die - lange zurückliegende - Verurteilung wegen Fahrens in angetrunkenem Zustand betreffe, habe sich der Beschwerdeführer 1 diesbezüglich wohlverhalten und sich nichts mehr zuschulden kommen lassen. Er habe regelmässig temporäre Arbeitseinsätze geleistet und sich immer wieder um eine Anstellung bemüht, was ihm entgegen den Prognosen der Migrationsbehörden dann schliesslich auch mit Erfolg gelungen sei. Seit Mai 2008 sei der Ehemann und Vater als Vollzeitarbeitnehmer beruflich vollständig integriert und erfülle auch seine Pflichten als Versorger. Die Ehefrau verdiene regelmässig mit; und dem Ehepaar gelinge es heute, selbständig und ohne zusätzliche Unterstützung für den Unterhalt ihrer Familie aufzukommen. Aufgrund der aktuellen Verhältnisse sei von einer guten Prognose auszugehen; eine Ausweisung aufgrund der vergangenen Fürsorgeabhängigkeit wäre unverhältnismässig und liege auch nicht im öffentlichen Interesse, was die Rückzahlung der bestehenden Verbindlichkeiten betreffe.
3.3 3.3.1 Zutreffend ist, dass nach <ref-law>, in der seit 1. Januar 2007 in Kraft stehenden Fassung, aus dem Strafregister entfernte Urteile dem Betroffenen nicht mehr entgegengehalten werden dürfen. An diese Urteile dürfen somit generell keine Rechtsfolgen mehr geknüpft werden (vgl. <ref-ruling> E. 2.10 mit Hinweisen; zur Publikation bestimmtes Urteil 6B_538/2008 vom 7. Januar 2009 E. 2.4-2.5). Dieses Verwertungsverbot von gelöschten Strafen gilt nicht nur für die Strafverfolgungsbehörden, sondern für sämtliche Behörden, die Strafregisterdaten aus VOSTRA beziehen (PATRICK GRUBER, Basler Kommentar, N 8/9 zu <ref-law>), somit auch für das Bundesamt für Migration (<ref-law>) und für die kantonalen Fremdenpolizeibehörden (<ref-law>). Bei der im Rahmen der Verhältnismässigkeitsprüfung vorzunehmenden ausländerrechtlichen Interessenabwägung kann indessen nicht ausgeblendet werden, wie sich der betroffene Ausländer während seiner gesamten Anwesenheit in der Schweiz verhalten hat. Für die ausländerrechtliche Interessenabwägung ist demnach das Verwertungsverbot gemäss <ref-law> insofern zu relativieren, als es den Fremdenpolizeibehörden nicht verwehrt ist, strafrechtlich relevante Daten, die sich in ihren Akten befinden oder ihnen anderweitig bekannt sind bzw. werden, namentlich solche, die Anlass zu einer fremdenpolizeilichen Verwarnung gaben, selbst nach deren Löschung im Strafregister in die Beurteilung des Verhaltens des Ausländers während seiner gesamten Anwesenheit in der Schweiz einzubeziehen, wobei selbstverständlich weit zurückliegenden Straftaten in der Regel keine grosse Bedeutung mehr zukommen kann (Urteile 2C_477/2008 vom 24. Februar 2009, E. 3.2.1 und 3.2.2, 2C_148/2009 vom 6. November 2009, E. 2.3).
3.3.2 Dies gilt vorliegend namentlich für die Verurteilung zu sechs Wochen Gefängnis und zu Fr. 800.-- Busse u.a. wegen Raufhandels aus dem Jahre 1998 (vorne lit. A). Die letzte Busse von Fr. 50.-- wegen Marihuana-Konsums vom 20. September 2007 betrifft kein Vergehen und fällt damit nicht unter Art. 10 Abs. 1 lit. a ANAG. Schliesslich bleibt die Vorstrafe wegen Fahrens in angetrunkenem Zustand aus dem Jahre 2002. Auch sie liegt relativ lange zurück und hat nicht das Gewicht, das für sich allein die Ausweisung der ganzen Familie zu rechtfertigen vermöchte. Immerhin darf nach dem Gesagten bei der vorzunehmenden Interessenabwägung mitberücksichtigt werden, dass die nicht unbedeutenden Vorstrafen, zu denen der Beschwerdeführer 1 verurteilt wurde, bereits zu zwei fremdenpolizeilichen Verwarnungen bzw. zur Androhung der Ausweisung geführt haben (vorne lit. A und E. 3.3.1).
3.4 Im Vordergrund stehen vorliegend aber zweifellos die Ausweisungsgründe von Art. 10 Abs. 1 lit. b (Unfähigkeit, sich in die im Gastland geltende Ordnung einzufügen) und lit. d ANAG (fortgesetzte erhebliche Fürsorgeabhängigkeit):
3.4.1 Die bisherige, an sich unbestrittene Schuldenwirtschaft der beiden Beschwerdeführer 1 und 2 erfüllt, wie das Verwaltungsgericht ohne Verletzung von Bundesrecht annehmen durfte, den Ausweisungsgrund von Art. 10 Abs. 1 lit. b ANAG (vgl. etwa Urteil 2A.436/2002 vom 26. Februar 2003, E. 2.2). Die zahlreichen Betreibungen und Verlustscheine betreffen beträchtliche Beträge, wobei die Beschwerdeführer die eingetretenen finanziellen Schwierigkeiten zum Teil bewusst in Kauf genommen haben, indem sie trotz ungesicherten Einkommensverhältnissen eine Familie gründeten und offensichtlich über ihre Verhältnisse gelebt hatten. Zwar sind in letzter Zeit soweit ersichtlich keine neuen Schulden dazugekommen. Die geäusserte Bereitschaft, "die Betreibungen bzw. die Verlustscheine in Raten abzuzahlen" (vgl. S. 5 der Beschwerdeschrift), kann angesichts der immer noch sehr knappen Einkommensverhältnisse (vgl. nachfolgende E. 3.4.2) aber nicht darüber hinwegtäuschen, dass die Gefahr einer weiteren gravierenden Schuldenwirtschaft nach wie vor besteht; im Übrigen beschränken sich die geltend gemachten Rückleistungen auf eine einzige Abschlagszahlung in Höhe von Fr. 150.-- an das Betreibungsamt.
Es mag zutreffen, dass die hier aktenkundigen Umstände über die Schuldenwirtschaft der Beschwerdeführer - ebenso wie die länger zurückliegenden strafrechtlichen Verurteilungen - für sich allein genommen nicht ausreichen, um die Ausweisung zu rechtfertigen. Im Rahmen der notwendigen Gesamtbetrachtung ist das bisherige Verhalten der Eheleute im Umgang mit ihren finanziellen Mitteln aber zu berücksichtigen (vorne E. 2.1).
3.4.2 Zu prüfen bleibt der Ausweisungsgrund von Art. 10 Abs. 1 lit. d ANAG:
Die Erheblichkeit der bereits bezogenen Fürsorgeleistungen wird von den Beschwerdeführern zu Recht nicht in Abrede gestellt (vgl. etwa <ref-ruling> E. 4 S. 533). Sie machen aber geltend, die Fürsorgeabhängigkeit bestehe nicht mehr und belegen dies mit einer Bestätigung der Sozialdienste Frauenfeld vom 14. August 2008, wonach der monatliche Lohn von A._ über dem sozialhilferechtlichen Existenzminimum liege und er heute keine Sozialhilfeunterstützung mehr benötige.
Für die Qualifikation einer Fürsorgeabhängigkeit als fortgesetzt im Sinne von Art. 10 Abs. 1 lit. d ANAG ist allerdings nicht so sehr von Bedeutung, ob gegenwärtig eine Fürsorgeabhängigkeit besteht. Entscheidend ist vielmehr, ob die Abhängigkeit zurückblickend - wie hier - einige Zeit andauerte, und ob die Befürchtung berechtigt ist, dass auch für die weitere Zukunft Unterstützung geleistet werden muss (Urteil 2C_795/2008 vom 25. Februar 2009, E. 4.2, mit Hinweis auf <ref-ruling> E. 3b). Erforderlich ist, dass aufgrund sämtlicher Umstände eine andauernde Unterstützungsbedürftigkeit konkret zu befürchten ist; blosse Bedenken genügen nicht (vgl. <ref-ruling> 3b S. 6 mit Hinweis; siehe auch <ref-ruling> E. 4 S. 532 f.; <ref-ruling> E. 3c S. 8; <ref-ruling> E. 2d S. 87).
Für die Beurteilung der Gefahr der Fürsorgeabhängigkeit ist von den aktuellen Verhältnissen auszugehen; die wahrscheinliche finanzielle Entwicklung ist aber auf längere Sicht abzuwägen. In diesem Sinne müssen die Erwerbsmöglichkeit und das damit verbundene Einkommen konkret belegt und mit gewisser Wahrscheinlichkeit sowie, soweit möglich, auf mehr als nur kurze Frist erhärtet sein, um Berücksichtigung zu finden (Urteile 2C_716/2007 vom 12. März 2008 E. 2.1, 2A.122/2007 vom 11. Juli 2007 E. 3.5 sowie 2A.119/1995 vom 24. August 1995 E. 6 b/aa).
Diese Voraussetzungen sind vorliegend nicht erfüllt: Im Zeitpunkt des angefochtenen Entscheides war der Beschwerdeführer 1 erst gerade ein halbes Jahr als Vollzeit-Arbeitnehmer (mit einem Monatslohn von Fr. 4'160.50) bei der R._ AG tätig; die Beschwerdeführerin 2 ihrerseits wird bei der Firma S._ bloss "auf Abruf" bzw. "nach Bedarf eingesetzt" (vgl. Arbeitsvertrag) und verfügt damit über kein gesichertes Einkommen. Das Verwaltungsgericht hat zudem - für das Bundesgericht grundsätzlich verbindlich (vorne E. 1.4) - festgestellt, dass A._ zuvor - soweit er überhaupt eine (temporäre) Erwerbstätigkeit ausgeübt hatte - am Arbeitsplatz mehrfach negativ aufgefallen war und jeweils erst dann Festanstellungen vorweisen konnte, wenn er wieder in Kontakt mit den fremdenpolizeilichen Behörden treten musste (vgl. S. 9 und 10 des angefochtenen Entscheides). Der Schluss des Verwaltungsgerichts, eine günstige Prognose könne nicht gestellt werden und es sei auch in Zukunft konkret eine Unterstützungsbedürftigkeit der Familie zu befürchten, ist unter diesen Umständen nicht zu beanstanden.
3.5 Die verfügte Ausweisung erweist sich auch nicht als unverhältnismässig: Beide Eheleute sind in Serbien aufgewachsen. Ihre besondere Integration in der Schweiz ist weder nachgewiesen noch ersichtlich; vielmehr mussten gegenüber dem Beschwerdeführer 1 bereits zwei fremdenpolizeiliche Verwarnungen ausgesprochen werden. Die Zwillingstöchter C._ und D._ (geboren 2003) befinden sich ausserdem noch in einem anpassungsfähigen Alter, so dass es auch den beiden Kindern zuzumuten ist, ihren Eltern ins Ausland zu folgen. Eine Verletzung von Art. 8 EMRK bzw. <ref-law> liegt nicht vor.
4. Nach dem Gesagten erscheint die gegenüber der Familie A._ - B._ verfügte Ausweisung im Lichte der gebotenen Gesamtbetrachtung nicht bundesrechtswidrig. Die kantonalen Behörden bewegten sich vorliegend vielmehr innerhalb des ihnen bei derartigen fremdenpolizeilichen Massnahmen zustehenden Spielraums (vgl. <ref-ruling> E. 2a S.523).
Dies führt zur Abweisung der Beschwerde.
Bei diesem Verfahrensausgang sind die Gerichtskosten den Beschwerdeführern unter solidarischer Haftung aufzuerlegen (Art. 65 und Art. 66 Abs. 1 BGG). Parteientschädigungen sind nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 1'500.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, dem Migrationsamt, dem Departement für Justiz und Sicherheit und dem Verwaltungsgericht des Kantons Thurgau sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 4. Dezember 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Klopfenstein