Sachverhalt:
A. Der mazedonische Staatsangehörige X._ (geb. 5. Mai 1962) heiratete in seinem Heimatland am 25. November 2004 die Schweizer Bürgerin Y._ (geb. 10. August 1982). Aus einer ersten am 28. September 2004 geschiedenen Ehe mit einer Landsfrau hat er fünf Kinder, die bei der Mutter in Mazedonien leben. X._ reiste am 12. Juni 2005 in die Schweiz ein, wo ihm aufgrund der Heirat eine Aufenthaltsbewilligung (letztmals verlängert bis zum 11. Juni 2008) erteilt wurde.
B. Mit Verfügung vom 30. Juni 2008 verweigerte das Ausländeramt des Kantons St. Gallen die Verlängerung der Aufenthaltsbewilligung von X._ mit der Begründung, es liege eine Scheinehe vor.
Dagegen beschwerte sich X._ ohne Erfolg beim Sicherheits- und Justizdepartement und sodann beim Verwaltungsgericht des Kantons St. Gallen.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 2. März 2009 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 22. Januar 2009 aufzuheben und die Aufenthaltsbewilligung zu verlängern. Zudem stellt er das Begehren, der Beschwerde aufschiebende Wirkung zu erteilen und dem Beschwerdeführer für das bisherige Verfahren eine angemessene Prozessentschädigung auszurichten.
Das Verwaltungsgericht des Kantons St. Gallen schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das Sicherheits- und Justizdepartement des Kantons St. Gallen sowie das Bundesamt für Migration beantragen, die Beschwerde abzuweisen.
D. Mit Verfügung vom 10. März 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung zuerkannt.

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 Gemäss Art. 42 Abs. 1 des auf den 1. Januar 2008 in Kraft getretenen, hier anwendbaren Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) haben ausländische Ehegatten von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen; nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren haben die Ehegatten Anspruch auf Erteilung der Niederlassungsbewilligung (Art. 42 Abs. 3 AuG).
Der Beschwerdeführer ist mit einer Schweizer Bürgerin verheiratet. Ob er mit ihr zusammen lebt, ist zweifelhaft, kann jedoch offen bleiben, da die Beschwerde ohnehin nicht durchdringt. Die Frage, ob die Bewilligung verweigert werden durfte, weil eine Schein- oder Ausländerrechtsehe vorliegt, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1b S. 266 mit Hinweisen).
1.3 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 (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Die Voraussetzungen für eine persönliche Anhörung der Eheleute sind nicht erfüllt, wobei ohnehin nicht ersichtlich ist, inwiefern eine nochmalige Befragung neue Erkenntnisse liefern könnte.
2. 2.1 Die Ansprüche nach Artikel 42 des Ausländergesetzes (vgl. vorne E. 1.2) erlöschen, wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen (Art. 51 Abs. 1 lit. a AuG). Hierunter fällt unter anderem die sogenannte Scheinehe oder Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen.
2.2 Ob eine Scheinehe geschlossen wurde, entzieht sich in der Regel dem direkten Beweis und ist bloss durch Indizien zu erstellen (<ref-ruling> E. 10.2 und 10.3 S. 135 f. mit Hinweis). Feststellungen über das Bestehen solcher Indizien können äussere Gegebenheiten, aber auch innere, psychische Vorgänge betreffen (Wille der Ehegatten); es handelt sich so oder anders um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (oben E. 1.3). Frei zu prüfen ist die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe bezwecke die Umgehung fremdenpolizeilicher Vorschriften oder sei rechtsmissbräuchlich (<ref-ruling> E. 2.3 S. 152 mit Hinweisen).
3. 3.1 Auf Grund der für das Bundesgericht verbindlichen Sachverhaltsfeststellungen (s. E. 1.3 hiervor) gelangte das Verwaltungsgericht des Kantons St. Gallen zur Auffassung, es liege eine Scheinehe vor. Dieser Schluss ist nicht zu beanstanden. Das Verwaltungsgericht konnte sich dafür auf zahlreiche Indizien stützen: Nur zwei Monate nach seiner Scheidung von seiner mazedonischen Ehefrau hat der Beschwerdeführer durch Vermittlung einer Drittperson seine schweizerische Ehefrau zwei Tage nach dem ersten Treffen in Mazedonien geheiratet. Ein Hochzeitsfest fand nicht statt und die schweizerische Ehefrau kehrte nach der Trauung sofort in die Schweiz zurück. Der Beschwerdeführer folgte ihr ungefähr ein halbes Jahr später und erhielt eine Aufenthaltsbewilligung, was ohne Heirat nicht möglich gewesen wäre. Seither wohnt er bei seinem Bruder in Zürich, wobei keine wichtigen Gründe für getrennte Wohnsitze ersichtlich sind (vgl. Art.49 AuG). Namentlich wird weder behauptet noch belegt, dass sich der Beschwerdeführer seit seiner Einreise in die Schweiz (erfolglos) bemüht hätte, in der Nähe des Wohnsitzes der Ehegattin eine Anstellung zu finden. Zudem ist aufgrund der beim Augenschein in der Wohnung der Ehegattin in Altstätten festgestellten Verhältnisse zweifelhaft, ob der Beschwerdeführer tatsächlich über das Wochenende dort wohnt. Weiter fällt auf, dass er mehrmals pro Jahr ohne seine Ehegattin ferienhalber nach Mazedonien zu seinen Kindern reiste, die bei seiner ehemaligen Ehefrau leben. Dem Umstand, dass er letztes Jahr erstmals Ferien mit seiner Ehefrau in Mazedonien verbrachte, kommt keine entscheidende Bedeutung zu, da es offensichtlich erst unter dem Druck der Nichtverlängerung der Aufenthaltsbewilligung zu dieser Reise kam. Mangelnde Kenntnisse betreffend den Ehepartner, der Altersunterschied von 20 Jahren und das Fehlen eines gemeinsamen Freundeskreises sowie gemeinsamer Freizeitbeschäftigungen sind weitere Indizien, die darauf hindeuten, dass vorliegend keine wirkliche eheliche Gemeinschaft gewollt war bzw. besteht. Die Einwendungen des Beschwerdeführers sind nicht geeignet, die tatsächlichen Feststellungen des Verwaltungsgerichts als offensichtlich unrichtig und die daraus gezogene Schlussfolgerung als bundesrechtswidrig erscheinen zu lassen.
3.2 Bei ihrer Befragung bestritt die Ehegattin im Grunde nicht, dass sie ursprünglich die Ehe eingegangen sei, um dem Beschwerdeführer den Aufenthalt in der Schweiz zu ermöglichen und ihn näher kennen zu lernen. Wie auch der Beschwerdeführer einräumt, sei die gegenseitige Zuneigung in der Folge gewachsen, weshalb heute eine echte Lebensgemeinschaft vorliege. Zwar ist nicht ausgeschlossen, dass eine ursprüngliche Scheinehe nachträglich zu einer echten Ehe werden kann, aus der ein Ausländer ein Aufenthaltsrecht ableiten darf (vgl. <ref-ruling> E. 2d S. 4 f.; Urteil 2C_703/2007 vom 19. März 2008 E. 3.6). Diesfalls müssen die Ehepartner jedoch ihren Willen, nunmehr eine echte Gemeinschaft zu bilden, in überzeugender Weise belegen, wofür eine gemeinsame Wohnadresse allein noch nicht ausreicht. Dies ist hier nicht geschehen. Konkrete Anhaltspunkte für eine derartige Entwicklung der ehelichen Beziehung sind vorliegend weder dargetan noch ersichtlich.
3.3 Nach dem Gesagten durfte die Vorinstanz ohne Verletzung von Bundesrecht oder staatsvertraglicher Garantien annehmen, bei der Ehe des Beschwerdeführers handle es sich um eine Scheinehe, und aus diesem Grund die Verlängerung der Aufenthaltsbewilligung verweigern. Für die Begründung kann ergänzend auf die Ausführungen im angefochtenen Urteil verwiesen werden (<ref-law>).
4. 4.1 Damit erweist sich die Beschwerde als offensichtlich unbegründet und ist im vereinfachten Verfahren nach <ref-law> abzuweisen, soweit darauf eingetreten werden kann.
4.2 Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (Art. 65 und Art. 66 BGG). Mit der Bestätigung des angefochtenen Urteils fällt eine Prozessentschädigung für das bisherige Verfahren von vornherein ausser Betracht.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Kantonalen Ausländeramt St. Gallen, dem Sicherheits- und Justizdepartement sowie dem Verwaltungsgericht des Kantons St. Gallen und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 20. Juli 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Müller Dubs