Sachverhalt:
A. Der 1983 geborene türkische Staatsangehörige X._ reiste am 27. Juni 2006 illegal in die Schweiz ein und stellte hier ein Asylgesuch, welches das Bundesamt für Migration am 27. Juli 2006 abwies. Gegen diesen Entscheid beschwerte sich X._ bei der damaligen Asylrekurskommission.
Im August 2006 lernte er die 14 Jahre ältere Schweizerin Y._ kennen und schloss mit ihr am 19. Januar 2007 die Ehe. Am 15. Februar 2007 stellte Y._ ein Gesuch um Familiennachzug für ihren Ehemann.
Am 18. Juni 2007 wurde die Beschwerde von X._ gegen den negativen Asylentscheid vom Bundesverwaltungsgericht, welches den Fall von der Asylrekurskommission übernommen hatte, abgewiesen.
Mit Verfügung vom 15. Oktober 2007 lehnte das Migrationsamt des Kantons Thurgau das Gesuch um Familiennachzug ab, da es die Verbindung zwischen X._ und Y._ als Scheinehe qualifizierte.
B. Gegen den abschlägigen Entscheid des Migrationsamtes rekurrierten X._ und Y._ ohne Erfolg beim Departement für Justiz und Sicherheit des Kantons Thurgau. Eine in der Folge eingereichte Beschwerde an das Verwaltungsgericht des Kantons Thurgau wies dieses mit Urteil vom 25. März 2009 ab.
C. Mit Eingabe vom 22. Mai 2009 führen X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie stellen den Antrag, es sei das vorinstanzliche Urteil aufzuheben und X._ eine Aufenthaltsbewilligung zu erteilen.
Das Migrationsamt, das Departement für Justiz und Sicherheit und das Verwaltungsgericht des Kantons Thurgau sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
Mit Verfügung vom 27. Mai 2009 erkannte der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zu.

Erwägungen:
1. Gemäss Art. 83 lit. c Ziff. 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.
Der Beschwerdeführer 1 hat aufgrund der geschlossenen Ehe mit einer Schweizerin gestützt auf Art. 7 Abs. 1 des Bundesgesetzes vom 26. Mai 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; in Kraft gewesen bis am 31. Dezember 2007), welches im vorliegenden Fall gemäss den übergangsrechtlichen Bestimmungen noch Anwendung findet (vgl. E. 2 hiernach), grundsätzlich einen Anspruch auf Erteilung der Aufenthaltsbewilligung. Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist daher grundsätzlich einzutreten. Ob die Verweigerung der nachgesuchten Bewilligung im vorliegenden Fall zulässig ist, bleibt Frage der materiellen Beurteilung.
2. Am 1. Januar 2008 ist das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) in Kraft getreten. Art. 126 Abs. 1 AuG bestimmt jedoch, dass auf Gesuche, die vor dem Inkrafttreten dieses Gesetzes eingereicht worden sind, noch das bisherige Recht anwendbar bleibt. Das vorliegend streitige Gesuch wurde vor Inkrafttreten des AuG gestellt und beurteilt sich daher noch nach dem inzwischen aufgehobenen ANAG und seinen Ausführungserlassen.
Gemäss Art. 7 Abs. 2 ANAG hat der ausländische Ehegatte einer Schweizer Bürgerin keinen Anspruch auf Erteilung einer Aufenthaltsbewilligung, wenn die Ehe zur Umgehung fremdenpolizeilicher Schranken geschlossen wurde (Scheinehe bzw. Ausländerrechtsehe, dazu ausführlich <ref-ruling> E. 2.1 S. 151; <ref-ruling> E. 4 und E. 5 S. 55 ff.). Eine Scheinehe liegt aber nicht bereits dann vor, wenn ausländerrechtliche Motive für den Eheschluss mitentscheidend waren. Erforderlich ist vielmehr, dass - zumindest bei einem der Ehepartner - der Wille zur Führung einer Lebensgemeinschaft von Anfang an nicht gegeben war (BGE <ref-ruling> E. 4a S. 55 mit Hinweisen; Urteil 2C_750/2007 vom 8. April 2008 E. 2.2).
Ob eine Scheinehe geschlossen wurde, entzieht sich oft einem direkten Beweis und ist bloss durch Indizien zu erstellen. Feststellungen des kantonalen Richters über das Bestehen von solchen Hinweisen können äussere Gegebenheiten, aber auch innere psychische Vorgänge betreffen (Wille der Ehegatten). In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG; <ref-ruling> E. 1.4.3 S. 254 f.). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, dass die Berufung auf die Ehe rechtsmissbräuchlich sei oder die Umgehung fremdenpolizeilicher Vorschriften bezwecke (<ref-ruling> E. 2.3 S. 152 mit Hinweisen). Für die Annahme einer Scheinehe bedarf es konkreter Hinweise, dass zumindest ein Ehegatte nicht eine eigentliche Lebensgemeinschaft führen will, sondern die Ehe nur aus fremdenpolizeilichen Überlegungen geschlossen hat. Diesbezügliche Indizien lassen sich praxisgemäss unter anderem darin erblicken, dass dem Ausländer die Wegweisung drohte, etwa weil er ohne Heirat keine Aufenthaltsbewilligung erhalten hätte oder sie ihm nicht verlängert worden wäre. Für das Vorliegen einer Ausländerrechtsehe können sodann die Umstände und die kurze Dauer der Bekanntschaft sprechen sowie insbesondere die Tatsache, dass die Ehegatten eine Wohngemeinschaft gar nie aufgenommen haben. Dasselbe gilt, wenn für die Heirat eine Bezahlung vereinbart wurde oder wenn ein erheblicher Altersunterschied zwischen den Ehepartnern besteht. Dass die Begründung einer wirklichen Lebensgemeinschaft gewollt war, kann umgekehrt nicht schon daraus abgeleitet werden, dass die Ehegatten während einer gewissen Zeit zusammenlebten und intime Beziehungen unterhielten; ein derartiges Verhalten kann auch nur vorgespielt sein, um die Behörden zu täuschen (<ref-ruling> E. 2b S. 295 mit Hinweisen).
3. Die Vorinstanzen weisen auf den ausländerrechtlichen Status des Beschwerdeführers 1 vor der Heirat hin und befinden, dass die Eheschliessung mit der Beschwerdeführerin 2 seine einzige Möglichkeit dargestellt habe, um sich ein Bleiberecht in der Schweiz zu verschaffen. Auffallend sei auch die kurze Dauer der Bekanntschaft der Beschwerdeführer vor der Heirat sowie der enge zeitliche Ablauf von Asylgesuch, Ablehnung desselben und Verheiratung. Ebenso erscheine der grosse Altersunterschied zwischen den Ehegatten als aussergewöhnlich. Die polizeiliche Befragung der Beschwerdeführer zeige zudem eine mangelnde Kenntnis der Lebensumstände sowie der Verwandtschaft und der Freundschaften des anderen Gatten auf. Der Beschwerdeführer 1 verbringe sodann einen Grossteil der Zeit nicht bei seiner (damals in E._ wohnhaften) Ehefrau, sondern bei seinem Onkel. Dieser betreibe in St. Gallen ein Grill-Restaurant, in welchem der Beschwerdeführer 1 illegal arbeite. Aus den genannten Gründen schliessen die Vorinstanzen darauf, dass der Wille zur Ehe und zum ehelichen Zusammenleben jedenfalls beim Beschwerdeführer 1 von Anfang an nicht vorhanden gewesen sei.
Die Beschwerdeführer bestreiten das Vorliegen einer Scheinehe und behaupten, dass der Ehewille bei beiden Gatten vorhanden sei. Die Vorinstanz habe die Beweise willkürlich gewürdigt. Insbesondere treffe es nicht zu, dass die Ehe nur deshalb geschlossen worden sei, weil der Beschwerdeführer 1 ansonsten keine Aufenthaltsbewilligung hätte erlangen können: Die Initiative zur Heirat sei vielmehr von der Beschwerdeführerin 2 ausgegangen und völlig unabhängig vom aufenthaltsrechtlichen Status des zukünftigen Ehemanns gewesen; vom hängigen Asylverfahren des Beschwerdeführers 1 habe die Beschwerdeführerin 2 überhaupt nichts gewusst. Auch könne keine Rede davon sein, dass die Ehe aufgrund des abschlägigen erstinstanzlichen Asylentscheids arrangiert worden sei: Die beiden Beschwerdeführer hätten sich im August 2006 kennengelernt, der negative Entscheid des Bundesamtes für Migration sei jedoch erst am 21. September 2006 ergangen. Entgegen der Ansicht der Vorinstanzen könne sodann nicht von einer auffällig kurzen Bekanntschaftszeit vor der Eheschliessung gesprochen werden, zumal sich die Beschwerdeführer zum Zeitpunkt der Heirat am 19. Januar 2007 bereits ca. sechs Monate gekannt hätten. Dies sei zwar nicht überlang, doch sei die Eheschliessung auch nicht überstürzt erfolgt. Der Altersunterschied habe überhaupt keine Rolle gespielt. Dem Vorhalt, nicht hinreichend über die persönlichen Verhältnisse der Ehepartner Bescheid zu wissen, entgegneten die Beschwerdeführer, sie hätten zwar nicht lückenlos über Vorleben und Hintergrund ihres Partners Auskunft geben können, doch hätten sie die wichtigsten Punkte gekannt. Im Übrigen sei die entsprechende polizeiliche Befragung lediglich zwei Monate nach Eheschliessung, d.h. nach einer Bekanntschaftszeit von insgesamt erst acht Monaten erfolgt; es liege auf der Hand, dass sie zu diesem Zeitpunkt noch keine umfassenden Kenntnisse über den Ehepartner gehabt hätten. Ohnehin sei es jedoch unzulässig, ausschliesslich auf diese eine Befragung abzustellen: Vielmehr müsse stattdessen gewürdigt werden, dass die Beschwerdeführer mittlerweile seit mehr als zwei Jahren in intakter Ehe zusammenlebten, was diverse Verwandte und Bekannte auch bestätigen könnten. Die Vorinstanz habe daher die in diesem Zusammenhang beantragte Befragung dieser Personen zu Unrecht abgelehnt, auf diese Weise das rechtliche Gehör der Beschwerdeführer verletzt und überdies den Sachverhalt offensichtlich unrichtig festgestellt.
4. 4.1 Die Ausführungen der Beschwerdeführer vermögen nicht zu überzeugen: Wie die Vorinstanzen zutreffend ausgeführt haben, war eine Eheschliessung die einzige Möglichkeit für den Beschwerdeführer 1, eine Aufenthaltsbewilligung für die Schweiz zu erhalten. Als er die Beschwerdeführerin 2 im August 2006 durch Vermittlung seines Onkels kennenlernte, war sein Asylgesuch vom Bundesamt für Migration bereits erstinstanzlich abgewiesen worden. Entgegen der aktenwidrigen Behauptung der Beschwerdeführer erging dieser Entscheid nicht erst am 21. September 2006, sondern bereits am 27. Juli 2006. Der Beschwerdeführer 1 wusste demzufolge schon bei der ersten Begegnung mit der Beschwerdeführerin 2, dass seine Aussichten, in der Schweiz Asyl zu erhalten, gering waren. Bestätigt wurde dies durch die Verfügung der damaligen Asylrekurskommission vom 11. September 2006, welche sein Gesuch um unentgeltliche Prozessführung unter Hinweis auf die Aussichtslosigkeit des erhobenen Rechtsmittels ablehnte. Wenn der Beschwerdeführer 1 vor diesem Hintergrund bereits nach einer Bekanntschaft von wenigen Monaten mit einer 14 Jahre älteren Schweizerin die Ehe schliesst, ist dieser Umstand - unabhängig davon, welcher der Ehepartner die Eheschliessung vorschlug - im Gesamtzusammenhang betrachtet durchaus als starkes Indiz für das Bestehen einer Umgehungsabsicht zu werten.
Als bedeutsam erachten durfte die Vorinstanz auch die Aussage der Beschwerdeführerin 2 anlässlich ihrer Befragung durch die Kantonspolizei Thurgau am 1. April 2007: Darin bringt die Beschwerdeführerin 2 zum Ausdruck, dass ihr Ehemann sehr oft nach St. Gallen fahre, um dort im Grill-Restaurant seines Onkels - verbotenerweise - einer Erwerbstätigkeit nachzugehen. In der Woche vor der Einvernahme sei er etwa bereits am Mittwoch weggefahren und erst am darauffolgenden Montagabend nach E._ zurückgekehrt. Die Beschwerdeführerin 2 gibt an, dass sie dieses Verhalten schon etwas störe, zumal sie ja nichts von ihrem Ehemann habe, wenn dieser fort sei. Sie habe ihn aus diesem Grund auch schon angesprochen, doch habe er dann jeweils nur gesagt, dass er arbeiten müsse. Weiter erklärt die Beschwerdeführerin 2, dass sie auch Weihnachten 2006 und Sylvester 2006/2007 nicht gemeinsam verbracht hätten, zumal ihr Ehemann auch an diesen Tagen in St. Gallen gearbeitet habe. Sie selbst habe sich dann freiwillig zum Dienst im Altersheim gemeldet, zumal sie nicht gewusst habe, was sie alleine zu Hause hätte tun sollen. Auf die Frage nach der letzten gemeinsamen Aktivität antwortete die Beschwerdeführerin 2, dass dies schon lange her sei; ca. 3-4 Wochen vor der Befragung seien sie gemeinsam in E._ einkaufen gegangen.
Diese Aussagen der Beschwerdeführerin 2 durfte die Vorinstanz - unbesehen der gegenteiligen Beteuerungen der Beschwerdeführer - dahingehend würdigen, dass es dem Beschwerdeführer 1 vor allem darum geht, sich in der Schweiz eine wirtschaftliche Existenz aufzubauen und er die Eheschliessung mit der Beschwerdeführerin 2 lediglich als Mittel zum Zweck erachtet hat, sich hier ein Aufenthaltsrecht zu sichern: Dass er trotz der vergleichsweise geringen Distanz zwischen St. Gallen und E._ offenbar nicht regelmässig zu seiner Ehefrau heimkehrte, ist ebenso auffällig, wie der Umstand, dass er wichtige Feierlichkeiten nicht im Rahmen der ehelichen Gemeinschaft verbrachte, sondern an diesen Tagen wiederum alleine nach St. Gallen reiste. Wer sich so verhält und das eheliche Zusammenleben ohne plausiblen Grund auf ein Minimum reduziert, kann nicht mit Erfolg das Vorhandensein eines wirklichen Ehewillens behaupten. Es ist demzufolge nicht willkürlich, wenn die Vorinstanz bei dieser Sachlage zum Schluss gelangt ist, der Beschwerdeführer 1 habe die Ehe mit der Beschwerdeführerin 2 nur geschlossen, um die ausländerrechtlichen Vorschriften zu umgehen. Die geschlossene Ehe begründet mithin keinen Rechtsanspruch des Beschwerdeführers 1 auf einen Aufenthaltstitel gemäss Art. 7 Abs. 1 ANAG.
4.2 Nicht durchzudringen vermag auch die vorgebrachte Rüge, die Vorinstanzen hätten den Anspruch auf rechtliches Gehör verletzt, indem sie die von den Beschwerdeführern beantragten Einvernahmen von Personen aus deren Verwandten- bzw. Bekanntenkreis ablehnten. Zwar beinhaltet der in <ref-law> gewährleistete Anspruch auf rechtliches Gehör u.a. auch das Recht der Betroffenen, mit erheblichen Beweisanträgen gehört zu werden (<ref-ruling> E. 3a S. 51 und 241 E. 2 S. 242, je mit Hinweisen). Jedoch ist dieser Anspruch nicht verletzt, wenn ein Gericht deshalb auf die Abnahme beantragter Beweismittel verzichtet, weil es aufgrund der bereits abgenommenen 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 (<ref-ruling> E. 3 S. 157; <ref-ruling> E. 2.1 S. 428; <ref-ruling> E. 4a S. 211, je mit Hinweisen).
Wie ausgeführt, stützt sich die Verweigerung der Aufenthaltsbewilligung für den Beschwerdeführer 1 in wesentlichem Ausmass auf die Angaben seiner eigenen Ehefrau, der Beschwerdeführerin 2. Inwiefern die Aussagen von aussenstehenden Drittpersonen geeignet wären, im vorliegenden Fall einen besseren Eindruck von den tatsächlichen Absichten des Beschwerdeführers 1 bzw. von inneren Tatsachen wie etwa dem Ehewillen zu vermitteln, ist nicht ersichtlich. Dies umso weniger, als die Personen, welche um Abgabe derartiger Auskünfte gebeten werden, den ersuchenden Personen gegenüber in aller Regel wohlwollend eingestellt sind und beabsichtigen, diesen zu helfen.
Dass das Verwaltungsgericht in dieser Situation auf die beantragten Einvernahmen verzichtet hat, ist daher nachvollziehbar und stellt jedenfalls weder eine Verletzung von <ref-law> noch einen Verstoss gegen das Willkürverbot von <ref-law> dar.
4.3 Die Beschwerdeführer behaupten sodann auch eine offensichtlich unrichtige Sachverhaltsfeststellung durch die Vorinstanz. Ihrer Begründung ist jedoch zu entnehmen, dass sie diesbezüglich wiederum beanstanden, dass das Verwaltungsgericht seine Feststellungen aufgrund der bereits vorhandenen Akten traf, und die gestellten Beweisanträge - insbesondere die anbegehrten Einvernahmen von Freunden und Verwandten der Beschwerdeführer - ablehnte. Dass diese Rüge nicht begründet ist, wurde bereits aufgezeigt (vgl. E. 4.2 hiervor).
5. Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen.
Da die Beschwerde von vornherein aussichtslos erschien, kann dem Gesuch um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren nicht entsprochen werden (<ref-law>). Somit sind die Gerichtskosten den Beschwerdeführern unter solidarischer Haftbarkeit aufzuerlegen (Art. 65 f. BGG). Eine Parteientschädigung ist nicht auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter Solidarhaft auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Thurgau und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 15. Oktober 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Zähndler