Sachverhalt:
A. X._ (geboren 1972) ist Staatsangehöriger von Bangladesch. Er reiste am 31. Oktober 2003 in die Schweiz ein und stellte ein Asylgesuch, welches das Bundesamt für Migration mit Entscheid vom 12. November 2003 abwies. Eine dagegen erhobene Beschwerde wies die damals zuständige Asylrekurskommission am 26. Februar 2004 ab. In der Folge setzte das Bundesamt für Migration X._ eine Ausreisefrist bis 30. April 2004; dieser befolgte die Aufforderung zur Ausreise nicht.
Am 2. Juli 2004 heiratete X._ die dominikanische Staatsangehörige Y._ (geboren 1973), welche über eine Niederlassungsbewilligung verfügt. Auf Gesuch hin erteilte das Ausländeramt des Kantons St. Gallen X._ am 11. Oktober 2005 eine Aufenthaltsbewilligung im Rahmen des Familiennachzugs.
B. Nach Einleitung von Ermittlungen wegen des Verdachts einer Scheinehe wies das Ausländeramt am 17. März 2008 das im Oktober 2007 eingereichte Gesuch von X._ um Verlängerung der Aufenthaltsbewilligung ab. Zur Begründung wurde vorgebracht, es liege eine Scheinehe vor. Dagegen erhob X._ Rekurs beim Sicherheits- und Justizdepartement des Kantons St. Gallen, welches mit Entscheid vom 4. Juli 2008 den Rekurs abwies. Mit Urteil vom 14. Oktober 2008 wies das Verwaltungsgericht des Kantons St. Gallen die gegen diesen Entscheid erhobene Beschwerde ab.
C. Mit Eingabe vom 19. November 2008 führt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, das Urteil der Vorinstanz vom 14. Oktober 2008 sei aufzuheben und es sei ihm die Aufenthaltsbewilligung zu erteilen. Gerügt wird die Verletzung des Anspruchs auf rechtliches Gehör sowie eine unrichtige Feststellung des Sachverhalts. Sodann ersucht er um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
D. Das kantonale Ausländeramt hat sich nicht vernehmen lassen. Das Sicherheits- und Justizdepartement und das Verwaltungsgericht des Kantons St. Gallen sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
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; BS 1 121) und seinen Ausführungserlassen.
1.3 Gemäss Art. 17 Abs. 2 Satz 1 ANAG (in der Fassung vom 23. März 1990) hat der ausländische Ehegatte eines niedergelassenen Ausländers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, solange die Ehegatten zusammen wohnen.
Als Ehegatte einer niedergelassenen Ausländerin steht dem Beschwerdeführer gestützt auf die erwähnte Bestimmung im Grundsatz ein Anspruch auf Verlängerung der Aufenthaltsbewilligung zu. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten erweist sich damit als zulässig (<ref-law>). Die Frage, ob die Bewilligung verweigert werden durfte, weil ein Fall von Rechtsmissbrauch, insbesondere eine Schein- bzw. Ausländerrechtsehe vorliegt, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1.1.5 S.150; <ref-ruling> E. 1b S. 266 mit Hinweisen).
1.4 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht - inklusive Bundesverfassungsrecht -, Völkerrecht sowie kantonale verfassungsmässige Rechte (<ref-law>). Das Bundesgericht legt 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 (<ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweist (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Nach Art. 7 Abs. 2 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers dann keinen Anspruch auf die ihm nach Abs. 1 dieser Bestimmung grundsätzlich zustehende Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen. Als Konkretisierung des Rechtsmissbrauchsverbots im Bereich ausländerrechtlicher Bewilligungen ist diese Regel über den Geltungsbereich von Art. 7 ANAG hinaus auch in Bezug auf die Ansprüche gemäss Art. 17 Abs. 2 ANAG in gleicher Weise anwendbar (<ref-ruling> E. 4.2 S. 117 mit Hinweisen). Art. 7 Abs. 2 ANAG bzw. der darin zum Ausdruck kommende Vorbehalt des Rechtsmissbrauchs bezieht sich auf die so genannte Schein- bzw. Ausländerrechtsehe. Ein Bewilligungsanspruch ist dann nicht gegeben, wenn zum Vornherein nie der Wille vorhanden war, eine dauerhafte Gemeinschaft zu begründen, und der einzige Zweck der Heirat darin besteht, dem Ausländer zu einer fremdenpolizeilichen Bewilligung zu verhelfen (vgl. <ref-ruling> E. 4a S. 55 mit Hinweisen).
2.2 Dass die Ehe nur (noch) formell und ohne Aussicht auf Aufnahme bzw. Wiederaufnahme einer ehelichen Gemeinschaft besteht, entzieht sich in der Regel einem direkten Beweis und ist oft bloss durch Indizien zu erstellen. Feststellungen des kantonalen Gerichts über diesbezügliche Indizien 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 verbindlich sind (vgl. E. 1.4). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften (<ref-ruling> E. 2.3 S. 152 mit Hinweisen).
Erforderlich sind konkrete Hinweise darauf, dass die Ehegatten nicht eine eigentliche Lebensgemeinschaft führen wollen, sondern die Ehe nur aus fremdenpolizeilichen Überlegungen eingegangen wurde (vgl. <ref-ruling> E. 5a S. 57). Diesbezügliche Indizien lassen sich u.a. 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. 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). Eine Scheinehe liegt demgegenüber 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.
3. 3.1 Der Beschwerdeführer rügt zunächst (sinngemäss) eine Verletzung des rechtlichen Gehörs. Er macht geltend, der angefochtene Entscheid beruhe im Wesentlichen auf den Aussagen der Eheleute X._. Gemäss Art. 13 des Gesetzes [des Kantons St. Gallen] vom 16. Mai 1965 über die Verwaltungsrechtspflege (VRP; sGS 951.1) seien für den Beweis durch Parteiaussagen und Zeugen die Vorschriften des Zivilprozessgesetzes [des Kantons St. Gallen] vom 20. Dezember 1990 (ZPG; sGS 961.2) anwendbar. Die Ehefrau des Beschwerdeführers hätte, da nicht Prozesspartei, als Zeugin befragt werden müssen. Dazu hätte man sie zur Wahrheit ermahnen und auf die Straffolgen von <ref-law> sowie das Zeugnisverweigerungsrecht aufmerksam machen müssen (Art. 109 ZPG). Dies sei nicht geschehen, weshalb ihre Aussagen nicht verwertbar seien (Art. 128 Abs. 2 ZPG).
Der Beschwerdeführer bringt diese Rüge soweit ersichtlich erstmals vor dem Bundesgericht vor. Es ist fraglich, ob damit nicht ein unzulässiges Novum vorliegt (vgl. E. 1.4). Die Frage kann indes offen bleiben, da sich die Rüge aus folgendem Grund als unbegründet erweist: Der Beschwerdeführer verkennt, dass seine Ehefrau - wie von der Vorinstanz in der Vernehmlassung dargelegt - nicht als Zeugin, sondern als Auskunftsperson gemäss Art. 12 Abs. 1 VRP befragt worden ist. Für die Befragung von Auskunftspersonen gelten aber nicht die gleichen Voraussetzungen wie für die Zeugenaussage; Art. 13 VRP verweist nur für Zeugen- und Parteiaussagen auf die Vorschriften des Zivilprozessgesetzes. Das Verwaltungsgericht durfte daher ohne in Willkür zu verfallen annehmen, die Aussagen der Ehefrau seien verwertbar. Eine Gehörsverletzung liegt insoweit nicht vor.
3.2 Der Beschwerdeführer bringt weiter vor, zufolge des Verzichts auf die beantragte Befragung von G._ (Vermieter) und H._ (Bekannter) habe die Vorinstanz das Beweisergebnis willkürlich gewürdigt und auch seinen Anspruch auf rechtliches Gehör verletzt.
Diese Begründung vermag jedoch nicht zu überzeugen: Wie bereits im vorinstanzlichen Entscheid (E. 3.4) dargelegt, durften die Behörden in willkürfreier antizipierter Beweiswürdigung auf die beantragte Einvernahme verzichten (vgl. <ref-ruling> E. 3 S. 157 mit Hinweisen). Sie durften insbesondere ohne Willkür annehmen, dass diese beiden Personen objektiv betrachtet keine entscheidrelevanten Tatsachen ins Verfahren einbringen konnten. Der Umstand, dass sich der Beschwerdeführer die letzten 14 Tage vor der polizeilichen Befragung praktisch täglich in der ehelichen Wohnung aufhielt - im Unterschied zu früher, als er offenbar arbeitsbedingt während fünf bis sechs Tagen in Zürich weilte - hat keine entscheidende Bedeutung, weil der Beschwerdeführer in diesem Zeitraum arbeitslos war. Aussagen von Bekannten haben im Weiteren regelmässig nur einen beschränkten Beweiswert, wenn - wie hier - davon auszugehen ist, diese seien dem Beschwerdeführer wohlgesonnen.
3.3 Der Beschwerdeführer macht geltend, auch die unterbliebene Wiederholung der Einvernahme der Ehefrau des Beschwerdeführers verletze seinen Anspruch auf rechtliches Gehör.
Dieser Einwand ist unbehelflich: Die Tatsache, dass sich die Ehefrau des Beschwerdeführers anlässlich der polizeilichen Einvernahme in schlechter psychischer Verfassung befand, macht ihre nochmalige Befragung nicht unumgänglich. Die Antworten der Ehefrau auf die Fragen scheinen klar, und revidierte Aussagen in Kenntnis der weiteren Verfahrensumstände wären kaum geeignet, zu belegen, dass die Aussagen in der polizeilichen Befragung auf Konzentrationsmängel oder situationsbedingten Gedächtnislücken beruhten. Die Vorinstanz durfte daher ohne Willkür auf dieses Beweisanerbieten verzichten und auf den wesentlichen Inhalt der Aussagen der Ehefrau abstellen.
3.4 Was der Beschwerdeführer weiter vorbringt, lässt die massgebenden Sachverhaltsumstände nicht als offensichtlich falsch erscheinen (vgl. E. 1.4).
Angesichts der zahlreichen Unstimmigkeiten in den Aussagen der Eheleute, ihrer geringen Kenntnisse der Lebensumstände des Ehepartners, der Verständigungsschwierigkeiten, der Art und Weise der Eheschliessung, des Fehlens gemeinsamer Freizeit- und Feriengestaltung und der weiteren Umstände (wie Verschweigen des hohen Spielgewinns und des vorübergehenden Verschwindens des Gewinnbetrags gegenüber dem Ehemann durch die Ehefrau, aber auch der Beherbergung anderer Männer in der ehelichen Wohnung durch die Ehefrau ohne Wissen des Ehemannes) durfte die Vorinstanz zum Schluss kommen, es liege eine Scheinehe, d.h. eine zur Verschaffung eines Aufenthaltstitels für den Beschwerdeführer eingegangene Ehe, vor. Die Verweigerung der Verlängerung der Aufenthaltsbewilligung durch die zuständigen kantonalen Behörden ist damit nicht zu beanstanden und erweist sich mithin als bundesrechtskonform.
4. Daraus ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist.
Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>); seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann mangels ernsthafter Erfolgsaussichten der Beschwerde nicht entsprochen werden (vgl. <ref-law>). Der wirtschaftlichen Situation des Beschwerdeführers wird indessen bei der Bemessung der Gerichtskosten Rechnung getragen.

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. 1'200.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, dem Ausländeramt, dem Sicherheits- und Justizdepartement und dem Verwaltungsgericht des Kantons St. Gallen sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 3. April 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger