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.