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. 