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.

Erwägungen:
1. 1.1 Gemäss Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
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, doch bestimmt dessen Art. 126 Abs. 1, dass auf Gesuche, die vor dem Inkrafttreten dieses Gesetzes eingereicht worden sind, noch das bisherige Recht anwendbar bleibt. Das streitige Gesuch wurde vor Inkrafttreten des Ausländergesetzes gestellt und beurteilt sich daher noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. Mai 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG) und seinen Ausführungserlassen.
1.3 Der Beschwerdeführer 1 hat aufgrund der am 24. November 2004 geschlossenen Ehe mit einer Schweizerin gestützt auf Art. 7 Abs. 1 ANAG einen grundsätzlichen Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung. Ein solcher grundsätzlicher Anspruch ergibt sich im Übrigen auch aus dem in Art. 8 Ziff. 1 EMRK bzw. Art. 13 Abs. 1 BV garantierten Schutz des Familienlebens, sofern die Ehe intakt ist und tatsächlich gelebt wird (<ref-ruling> E. 1d/aa S. 64 f.).
2. 2.1 Kein Anspruch auf eine Aufenthaltsbewilligung besteht, wenn die Ehe zur Umgehung fremdenpolizeilicher Schranken geschlossen wurde (Scheinehe bzw. Ausländerrechtsehe, Art. 7 Abs. 2 ANAG, dazu ausführlich <ref-ruling> E. 2.1 S. 151; <ref-ruling> E. 4 und 5 S. 55 ff.); der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt (Art. 7 Abs. 1 Satz 3 ANAG).
Für die Annahme einer Scheinehe bedarf es konkreter Hinweise darauf, dass die Ehegatten nicht eine eigentliche Lebensgemeinschaft führen wollen, sondern die Ehe nur aus fremdenpolizeilichen Überlegungen eingegangen wurde (vgl. BGE <ref-ruling> E. 5a S. 57). Eine Scheinehe liegt aber nicht bereits dann vor, wenn ausländerrechtliche Motive für den Eheschluss mitentscheidend waren. Erforderlich ist zusätzlich, dass der Wille zur Führung einer Lebensgemeinschaft - zumindest bei einem der Ehepartner - von Anfang an nicht gegeben ist (BGE <ref-ruling> E. 4a S. 55 mit Hinweisen, Urteil 2C_750/2007 vom 8. April 2008, E. 2.2). Es ist Sache der Fremdenpolizeibehörden, eine Scheinehe nachzuweisen; liegen hiefür nicht genügend konkrete Indizien vor, darf nicht auf eine solche geschlossen werden.
Für eine Scheinehe, wie sie vom kantonalen Departement behauptet wird, bestehen im hier zu beurteilenden Fall nicht genügend objektive Indizien. Wohl besteht Anlass zur Vermutung, dass der Beschwerdeführer 1, der hier erfolglos ein Asylgesuch gestellt hatte und ausgeschafft werden musste, sich mit der eingegangenen Ehe in erster Linie ein Aufenthaltsrecht in der Schweiz verschaffen will. Die ungefähr im gleichen Alter stehende schweizerische Ehefrau hat jedoch gemäss den Akten (Passkopien) vom 21. Juli 2004 bis zum 7. April 2005 in Gambia gelebt und dort während dieses längeren Aufenthaltes am 24. November 2004 den Beschwerdeführer 1 geheiratet. Seither verbringt sie regelmässig ihre Ferien bei ihrem Ehemann in Gambia (vom 29. September 2005 bis zum 20. Oktober 2005, vom 6. Juni 2006 bis zum 11. Juli 2006, vom 15. März 2007 bis zum 16. April 2007 sowie vom 9. Oktober 2007 bis zum 7. November 2007). Im Übrigen stehen die Eheleute in engem telefonischen Kontakt: Gemäss unwidersprochener Darstellung will die Beschwerdeführerin 2 seit 2005 für Telefonate mit ihrem Ehemann rund Fr. 3'500.-- ausgegeben haben. Der Beschwerdeführer 1 bemühte sich seinerseits mehrfach um die Aufhebung der gegen ihn verfügten Einreisesperre ausdrücklich auch deshalb, um seine Ehefrau sehen zu können.
Es fehlen bei dieser Sachlage genügende Indizien, um auf einen fehlenden Willen zur Führung einer echten ehelichen Lebensgemeinschaft schliessen zu können. In einem solchen Falle muss trotz bestehender Zweifel gestützt auf Art. 7 ANAG dem ausländischen Ehegatten die Aufenthaltsbewilligung erteilt werden, auf das Risiko hin, dass sich die Ehe aufgrund des späteren Verhaltens der Beteiligten (z.B. fehlendes eheliches Zusammenleben in der Schweiz) in Verbindung mit den bereits heute bekannten, in diese Richtung weisenden Indizien als Scheinehe herausstellt und die Aufenthaltsbewilligung gestützt auf die dannzumaligen Erkenntnisse widerrufen werden muss bzw. nicht mehr zu verlängern ist (Urteil 2C_750/2007 vom 8. April 2008).
2.2 Zu prüfen bleibt, ob gegen den Beschwerdeführer 1 ein Ausweisungsgrund vorliegt, der seinen aus Art. 7 ANAG folgenden Anspruch auf Aufenthalt bei seiner Ehefrau in der Schweiz zum Erlöschen bringen würde (vorne E. 2.1).
Der Beschwerdeführer 1 wurde nach Gambia ausgeschafft, bevor die gegen ihn wegen angeblicher Verstösse gegen das Betäubungsmittelgesetz veranlassten Ermittlungen durchgeführt werden konnten. Er wurde zwar - wegen Missachtens einer Eingrenzung - bereits einmal zu einer Busse verurteilt, eine strafrechtliche Verurteilung im Sinne von Art. 10 Abs. 1 lit a ANAG ("gerichtliche Bestrafung") liegt aber nicht vor; der blosse Verdacht des Kokainhandels reicht aufgrund der geltenden Unschuldsvermutung nicht aus. Sodann erlaubt das vom Beschwerdeführer 1 während des Asylverfahrens gezeigte Fehlverhalten (unwahre Angaben zur Herkunft, Marihuanakonsum bzw. -handel, Missachtung einer Eingrenzung) für sich allein noch nicht die Annahme, er sei als Ehemann einer Schweizerin nicht gewillt oder nicht fähig, sich in die hiesige Ordnung einzufügen (so der Ausweisungsgrund von Art. 10 Abs. 1 lit. b ANAG); sein Anspruch auf eine Anwesenheitsbewilligung erlischt nicht schon dann, wenn er "gegen die öffentliche Ordnung verstossen hat", wie dies beim Ehemann einer Niedergelassenen der Fall wäre (Art. 17 Abs. 2 ANAG), sondern erst, wenn ein Ausweisungsgrund vorliegt (vorne E. 2.1). Schliesslich kann auch nicht unterstellt werden, dass der Beschwerdeführer 1 als Ehemann einer erwerbstätigen Schweizer Bürgerin fortgesetzt und in erheblichem Masse der öffentlichen Wohlfahrt zur Last fallen wird (Art. 10 Abs. 1 lit. d ANAG).
2.3 Das Verwaltungsgericht begründet die Verweigerung der anbegehrten Aufenthaltsbewilligung einzig damit, dass gegen den Beschwerdeführer 1 eine noch bis zum 4. April 2009 geltende rechtskräftige Einreisesperre bestehe, deren Aufhebung vom zuständigen Bundesamt zweimal abgelehnt worden sei. Bei dieser Sachlage sei das kantonale Migrationsamt befugt gewesen, die Erteilung einer Aufenthaltsbewilligung zu verweigern, zumal eine solche sinnlos wäre, wenn der Gesuchsteller gar nicht einreisen dürfe.
Das Vorliegen einer Einreisesperre steht gemäss der bundesgerichtlichen Praxis der Geltendmachung und allfälligen Anerkennung eines Rechtsanspruches auf Erteilung einer Aufenthaltsbewilligung nicht entgegen. Kommt die zuständige Bewilligungsbehörde (oder die angerufene Rechtsmittelinstanz) zum Schluss, dass ein Rechtsanspruch auf Zulassung des Aufenthaltes besteht, kann und muss sie die anbegehrte Anwesenheitsbewilligung erteilen; sie darf dabei davon ausgehen, dass ein der Ausübung dieses Rechtes entgegenstehendes Einreiseverbot von der hiefür zuständigen Behörde aufgrund pflichtgemässen Ermessens aufgehoben wird (Urteil 2A.141/2002 vom 19. Juli 2002, E. 1.2, Andreas Zünd, in: Uebersax/Münch/Geiser/Arnold, Ausländerrecht, Basel 2002, Rz. 6.84). Diese Betrachtungsweise drängt sich aus Gründen der Kohärenz der Rechtsordnung jedenfalls dann auf, wenn die zum Einreiseverbot führenden Umstände bei der Erteilung der Aufenthaltsbewilligung bekannt waren und in die Interessenabwägung eingeflossen sind. Ob und unter welchen Voraussetzungen eine Einreisesperre von den hiefür zuständigen Behörden aufgrund eigener abweichender Beurteilung ausnahmsweise auch entgegen einer erteilten Anwesenheitsbewilligung verfügt oder aufrecht erhalten werden könnte, braucht nicht untersucht zu werden, da Gründe für ein derartiges Vorgehen hier nicht in Betracht fallen. Die dem angefochtenen Urteil des Verwaltungsgerichts zugrunde liegende Annahme, die gegen den Beschwerdeführer 1 verfügte Einreisesperre stehe der Erteilung der anbegehrten Aufenthaltsbewilligung entgegen, verstösst gegen Bundesrecht.
3. Nach dem Gesagten ist die vorliegende Beschwerde gutzuheissen und das angefochtene Urteil des Verwaltungsgerichts aufzuheben.
Heisst das Bundesgericht die Beschwerde gut, so entscheidet es in der Sache selbst oder weist diese zu neuer Beurteilung an die Vorinstanz zurück. Es kann die Sache auch an die Behörde zurückweisen, die als erste Instanz entschieden hat (Art. 107 Abs. 2 BGG).
Nachdem das vorliegende Verfahren seit der Einreichung des ersten Familiennachzugsgesuches über dreieinhalb Jahre gedauert hat, erscheint es angezeigt, die Sache an das Migrationsamt des Kantons Thurgau zurückzuweisen. Dieses hat dem Beschwerdeführer 1 die anbegehrte Aufenthaltsbewilligung ohne Verzug zu erteilen. Beizufügen bleibt in diesem Zusammenhang, dass der Beschwerdeführer 1 bei einer allfälligen strafrechtlichen Verurteilung mit der Möglichkeit des Widerrufs oder der Nichtverlängerung seiner Aufenthaltsbewilligung rechnen muss, wobei sein bisheriges Verhalten in der Schweiz bei der dannzumal vorzunehmenden Beurteilung mitberücksichtigt werden darf.
Ferner wird es Sache des Verwaltungsgerichts sein, über die Kosten des kantonalen Rechtsmittelverfahrens neu zu befinden.
Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 66 Abs. 4 BGG). Hingegen hat der Kanton Thurgau die obsiegenden Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Thurgau vom 21. Mai 2008 aufgehoben.
2. Die Sache wird zur Erteilung der anbegehrten Aufenthaltsbewilligung an das Migrationsamt des Kantons Thurgau zurückgewiesen.
3. Das Verwaltungsgericht des Kantons Thurgau hat über die Kosten des kantonalen Rechtsmittelverfahrens neu zu befinden.
4. Es werden keine Gerichtskosten erhoben.
5. Der Kanton Thurgau hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
6. 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, 17. November 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber
Merkli Klopfenstein