Sachverhalt: A. Der aus Gambia stammende X._ (geb. 1982) reiste am 21. Dezember 2000 als Asylbewerber in die Schweiz ein. Das damalige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) trat auf sein Asylgesuch nicht ein und wies ihn aus der Schweiz weg. Eine hiegegen erhobene Beschwerde wies die Schweizerische Asylrekurskommission mit Urteil vom 10. Juni 2002 ab, soweit sie darauf eintrat. Am 5. Mai 2004 wurde X._ nach Gambia ausgeschafft, nachdem das zuständige Bundesamt gegen ihn tags zuvor eine bis zum 3. Mai 2009 gültige Einreisesperre verfügt hatte. Während seiner Anwesenheit in der Schweiz war X._ verschiedentlich polizeilich aufgefallen. Bei ihm fanden sich 16 Gramm Marihuana und es war der Verdacht entstanden, er habe mit "mehreren hundert Gramm" Kokain gehandelt, weswegen die zuständigen thurgauischen Polizeibehörden am 29. April 2004 Ermittlungen gegen ihn veranlassten, welche aufgrund der Ausschaffung "nicht mehr durchgeführt werden" konnten (vgl. Bericht der Kantonspolizei Thurgau vom 5. Mai 2004). X._ hatte auch eine gegen ihn am 13. März 2003 ergangene Eingrenzungsverfügung missachtet, wofür er am 2. Februar 2004 vom Bezirksamt Steckborn mit einer Busse von Fr. 60.-- bestraft worden war. B. Am 24. November 2004 heiratete X._ in Gambia die Schweizer Bürgerin Y._ (geb. 1983), die er während seiner Anwesenheit als Asylsuchender in der Schweiz kennen gelernt hatte. Die hier erwerbstätige Y._ lebte in Gambia rund acht Monate mit ihrem Ehemann zusammen, bevor sie am 8. April 2005 in die Schweiz zurückkehrte und für ihn gleichentags ein Familiennachzugsgesuch stellte. Vom zuständigen Ausländeramt des Kantons Thurgau erhielt sie in der Folge den Bescheid, die Wiedereinreise ihres Mannes sei nicht erwünscht und dieser müsse bei einer Rückkehr mit Ermittlungen wegen Drogenhandels rechnen. X._ liess daraufhin - am 19. Juli 2005 - ein Gesuch um Suspendierung der Einreisesperre stellen, damit er am Strafverfahren teilnehmen und seine Ehefrau sehen könne. Mit Verfügung vom 16. August 2005 wies das Bundesamt für Migration dieses Gesuch ab; es kam auch wiedererwägungsweise (Gesuch vom 20. Juli 2006, Verfügung vom 2. August 2006) nicht darauf zurück, nachdem das Eidgenössische Justiz- und Polizeidepartement mit Entscheid vom 8. Mai 2006 eine Beschwerde gegen die Verfügung vom 16. August 2005 abgewiesen hatte. Mit Eingabe vom 22. November 2006 wandten sich die - inzwischen durch einen anderen Anwalt vertretenen - Eheleute X und Y erneut an die Thurgauer Behörden und beantragten den Familiennachzug des Ehemannes gestützt auf Art. 7 ANAG. Mit Entscheid vom 11. Januar 2007 wies das Migrationsamt das Gesuch ab, wogegen die Eheleute X und Y beim Departement für Justiz und Sicherheit des Kantons Thurgau Rekurs erhoben. Da innert angemessener Frist kein Entscheid erging, gelangten sie mit einer Rechtsverzögerungsbeschwerde ans kantonale Verwaltungsgericht und, als sich auch dort das Verfahren in die Länge zog, mit Beschwerde vom 4. Februar 2008 wegen Rechtsverweigerung und Rechtsverzögerung (Art. 94 BGG) ans Bundesgericht. Dieses Verfahren wurde, nachdem das kantonale Verwaltungsgericht die bei ihm hängige Rechtsverzögerungsbeschwerde am 13. Februar 2008 gutgeheissen hatte, am 3. März 2008 zufolge Dahinfallens des Rechtsschutzinteresses abgeschrieben (Verfahren 2C_134/2008). C. Mit Entscheid vom 29. Februar 2008 wies das Departement für Justiz und Sicherheit des Kantons Thurgau den Rekurs gegen die Verweigerung des Familiennachzugs ab. Zur Begründung erwog es im Wesentlichen, X._ habe mit seinem Verhalten als Asylsuchender in der Schweiz gezeigt, dass er nicht gewillt oder nicht fähig sei, sich in die hier geltende Rechts- und Gesellschaftsordnung einzufügen. Sodann lägen gewichtige Indizien für eine Scheinehe vor bzw. jedenfalls dafür, dass es zumindest beim Ehemann an der Absicht fehle, eine echte Lebensgemeinschaft zu gründen; diesem gehe es allein um die Möglichkeit der Wiedereinreise in die Schweiz. Somit liege ein Ausweisungsgrund nach Art. 10 Abs. 1 lit. b ANAG sowie eine Scheinehe gemäss Art. 7 Abs. 2 ANAG vor, weshalb die Aufenthaltsbewilligung für den Ehemann zu verweigern sei. Eine hiegegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Thurgau mit Entscheid vom 21. Mai 2008 ab. D. Mit Eingabe vom 27. Juni 2008 führen die Eheleute X und Y beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, den Entscheid des Verwaltungsgerichts des Kantons Thurgau aufzuheben, X._ die Einreise in die Schweiz zu bewilligen und ihm hernach eine Aufenthaltsbewilligung zu erteilen; eventuell sei der angefochtene Entscheid aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Ausserdem seien die kantonalen Instanzen anzuweisen, entstandene Anwaltskosten im Betrag von insgesamt Fr. 7'921.30 zu ersetzen; eventuell sei die Sache auch zur Festsetzung der Entschädigungen an die Vorinstanz zurückzuweisen. Das Migrationsamt des Kantons Thurgau beantragt, die Beschwerde abzuweisen. Denselben Antrag stellen das kantonale Departement für Justiz und Sicherheit sowie das kantonale Verwaltungsgericht. Das Bundesamt für Migration schliesst auf Gutheissung der Beschwerde.