Sachverhalt:
A. Der mazedonische Staatsangehörige X._ (geb. 3. Mai 1969) reiste am 12. Februar 2000 in die Schweiz ein und heiratete am 9. Mai 2000 in St. Gallen die Schweizer Bürgerin Y._ (geb. 19. September 1967). Gestützt auf die Heirat wurde ihm eine Aufenthaltsbewilligung erteilt. Im Jahr 2003 trennten sich die Ehegatten, wobei sie am 15. Januar 2003 eine aussergerichtliche Trennungsvereinbarung abschlossen. Am 14. Oktober 2005 erhielt X._ die Niederlassungsbewilligung. Die Ehe von X._ und Y._ wurde am 30. Juni 2006 geschieden.
Am 18. Juli 2006 heiratete X._ in Mazedonien die Landsfrau Z._ (geb. 4. Juli 1973), mit der er vier gemeinsame Kinder (geb. 1991, 1993, 1996, 1998) hat. Z._ ist zudem Mutter des am 25. März 2003 geborenen Sohnes A._.
Am 10. November 2006 wurde X._ vom Ausländeramt des Kantons St. Gallen befragt; dabei verschwieg er sowohl die Geburt des Sohnes A._, obwohl er im amtlichen Register als dessen Vater eingetragen war, als auch die Heirat mit der Mutter seiner Kinder und gab an, er habe keine neue Partnerin.
Die Ehe X._ und Z._ wurde am 21. März 2007 durch das Amtsgericht F._ wieder geschieden. Am 4. April 2007 heirateten X._ und Z._ in Mazedonien erneut. X._ stellte darauf ein Familiennachzugsgesuch für seine Ehefrau und die fünf Kinder.
Am 26. Juli 2007 heiratete Y._ in Bosnien Herzegowina einen bosnischen Staatsangehörigen, den sie 1996 in St. Gallen kennengelernt hatte und mit dem sie gemäss ihren eigenen Angaben seit dem Jahre 2003 eine feste Beziehung pflegt.
B. Mit Verfügung vom 8. September 2008 widerrief das Ausländeramt des Kantons St. Gallen die Niederlassungsbewilligung von X._ mit der Begründung, er sei mit Y._ eine Scheinehe eingegangen.
Den dagegen von X._ erhobenen Rekurs wies das Sicherheits- und Justizdepartement des Kantons St. Gallen mit Entscheid vom 8. Dezember 2008 ab. Ohne Erfolg beschwerte sich X._ gegen den Rekursentscheid beim Verwaltungsgericht des Kantons St. Gallen. Im Beschwerdeverfahren vor dem Verwaltungsgericht reichte er ein Urteil des Amtsgerichts G._ vom 14. Juli 2009 ein, wonach er nicht der leibliche Vater des Kindes A._ ist.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 22. September 2009 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 19. August 2009 aufzuheben und vom Widerruf der Niederlassungsbewilligung abzusehen. Weiter stellt er das Begehren, die Sache an die Vorinstanz und anschliessend an die Rekursinstanz zurückzuweisen zur Festlegung einer Parteientschädigung für das vorinstanzliche Verfahren bzw. das Rekursverfahren. Zudem beantragt er, der Beschwerde die aufschiebende Wirkung zu erteilen, eventuell ihm im Rahmen einer vorsorglichen Massnahme den Aufenthalt während der Dauer des Beschwerdeverfahrens zu bewilligen.
Das Verwaltungsgericht des Kantons St. Gallen beantragt, die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Das Sicherheits- und Justizdepartement des Kantons St. Gallen und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
D. Mit Verfügung vom 24. September 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Nach Art. 83 lit. c Ziff. 2 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. Gegen Entscheide über den Widerruf oder die Feststellung des Erlöschens einer Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (<ref-ruling> E. 1.2.1 S. 4. mit Hinweis). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde kann daher eingetreten werden.
1.2 Am 1. Januar 2008 ist das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [Ausländergesetz, AuG; SR 142.20]) in Kraft getreten, womit das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) aufgehoben wurde. Nach Art. 126 AuG richtet sich der Widerruf der fraglichen Niederlassungsbewilligung nach den Bestimmungen des neuen Ausländergesetzes.
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). 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 Art. 95 BGG beruht (Art. 97 Abs. 1 BGG bzw. Art. 105 Abs. 2 BGG). 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 (Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG).
2. 2.1 Sowohl nach Art. 7 Abs. 1 ANAG (gültig bis 31. Dezember 2007) als auch nach Art. 42 Abs. 1 AuG hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wobei das Ausländergesetz zusätzlich verlangt, dass er mit diesem zusammenwohnt; des Weiteren hat er nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren Anspruch auf die Niederlassungsbewilligung (Art. 7 Abs. 1 Satz 2 ANAG; Art. 42 Abs. 3 AuG). Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern zu umgehen (Art. 7 Abs. 2 ANAG; Art. 51 Abs. 1 AuG). Erfasst wird davon die sogenannte Scheinehe bzw. Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen (<ref-ruling> E. 2.1 S. 151 mit Hinweisen). Der Anspruch entfällt darüber hinaus auch bei rechtsmissbräuchlicher Berufung auf eine nur noch formell und ohne Aussicht auf Aufnahme bzw. Wiederaufnahme einer ehelichen Gemeinschaft bestehende Ehe (<ref-ruling> E. 2.2 S. 151 mit Hinweisen). Als eigenes und selbständiges Niederlassungsrecht erlischt die einmal erteilte Niederlassungsbewilligung nicht mit der Auflösung der Ehe. Sie kann aber widerrufen werden.
2.2 Die Niederlassungsbewilligung kann widerrufen werden, wenn der Ausländer im Bewilligungsverfahren falsche Angaben gemacht oder wesentliche Tatsachen verschwiegen hat (Art. 62 lit. a AuG; Art. 9 Abs. 4 lit. a ANAG). Der Widerruf setzt voraus, dass der Betroffene wissentlich falsche Angaben gemacht oder wesentliche Tatsachen verschwiegen hat, in der Absicht, gestützt darauf den Aufenthalt oder die Niederlassung bewilligt zu erhalten. Nach Art. 90 lit a AuG (Art. 3 Abs. 2 ANAG) ist der Ausländer verpflichtet, der Behörde über alles, was für den Bewilligungsentscheid massgebend sein kann, wahrheitsgetreu Auskunft zu geben. Wesentlich sind dabei nicht nur Umstände, nach denen die Fremdenpolizei ausdrücklich fragt, sondern auch solche, von denen der Gesuchsteller wissen muss, dass sie für den Bewilligungsentscheid relevant sind (vgl. <ref-ruling> E. 4.1 S. 9). Das Erschleichen einer Niederlassungsbewilligung durch falsche Angaben oder durch wissentliches Verschweigen von Tatsachen kann schon darin liegen, dass die Angaben, auf welche sich die Behörden bei der seinerzeitigen Bewilligungserteilung gestützt hatten oder die bei späteren Verlängerungen der Aufenthaltsbewilligung oder bei der Erteilung der Niederlassungsbewilligung mangels anderer Angaben immer noch als massgebend betrachtet werden konnten, falsch oder unvollständig waren (Urteile 2C_311/2009 vom 5. Januar 2010 E. 2.2; 2C_33/2008 vom 7. Mai 2008 E. 3.2; 2A.33/2007 vom 9. Juli 2007 E. 4.1; 2A.129/2006 vom 27. Juni 2006 E.2.2; 2A.436/2003 vom 6. Januar 2004 E. 3.1; <ref-ruling> E. 3b S. 475 f.; je mit Hinweisen).
Bei eigentlichen Machenschaften wie dem Eingehen einer Scheinehe bedarf es keiner ausdrücklichen Frage der Ausländerbehörde. Die Bewilligung gilt ohne weiteres als erschlichen (vgl. Urteil 2A.595/2006 vom 6. Februar 2007 E. 4.4 und 4.5; Andreas Zünd/Ladina Arquint Hill, in: Uebersax/Rudin/Hugi Yar/Geiser, Ausländerrecht, 2. Auflage, 2008, Rz. 8.27).
2.3 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 (vgl. E. 1.3 hiervor). 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).
2.4 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. 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 vorgespiegelt 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 war (<ref-ruling> E. 4a S. 55 mit Hinweisen; Urteil 2C_446/2009 vom 23. November 2009 E. 2.2).
2.5 Das Verwaltungsgericht geht in seinem Entscheid von der dargestellten Rechtsprechung aus und hat diese korrekt angewandt.
Für die Annahme, der Beschwerdeführer sei mit seiner vormaligen schweizerischen Ehefrau eine Scheinehe eingegangen, konnte sich die Vorinstanz auf zahlreiche Indizien stützen: Der Beschwerdeführer hätte sich ohne Heirat kein Anwesenheitsrecht in der Schweiz verschaffen können. Die Ehegatten machten widersprüchliche Aussagen unter anderem betreffend die Hochzeit, die Flitterwochen sowie angebliche gemeinsame Ferien in Mazedonien. Die Auskünfte der schweizerischen Ehefrau bezüglich der Geschwister des Beschwerdeführers waren unzutreffend. Weiter behaupteten die Ehegatten nach der Trennung im Jahre 2003, sie beabsichtigten die Wiederaufnahme des ehelichen Zusammenlebens, was sich im Nachhinein als offensichtlich falsch erwies. Eigenen Angaben zufolge pflegte die schweizerische Ehegattin nämlich bereits damals eine feste Beziehung zu ihrem heutigen Ehemann. Zudem hatte der Beschwerdeführer seinerseits die eheähnliche Parallelbeziehung zur Mutter seiner Kinder offensichtlich die ganze Zeit weitergeführt, was die Heirat nur 18 Tage nach der Scheidung von der schweizerischen Ehefrau erklärt. Zwar ist nicht entscheidwesentlich, ob der Beschwerdeführer der leibliche Vater des 2003 geborenen Kindes ist oder nicht, aber immerhin fällt auf, dass er im kantonalen Rekursverfahren noch geltend machte, es sei nicht klar, ob er der Vater dieses Kindes sei, und damit implizit diese Möglichkeit selber nicht auszuschliessen schien. Befremdend ist auch, dass er im heimatlichen Register als Vater eingetragen war, obwohl er mit der Kindsmutter damals nicht verheiratet war, und dass er dennoch erst im Beschwerdeverfahren vor dem Verwaltungsgericht ein gegenteiliges heimatliches Urteil einreichte. Auch die Scheidung von der mazedonischen Ehefrau am 21. März 2007 und die erneute Heirat mit ihr am 4. April 2007 stehen eindeutig im Zusammenhang mit den Vorkehren, die auf eine Scheinehe hindeutenden tatsächlichen familiären Umstände (Parallelbeziehung mit heutiger Ehefrau während der Ehe mit der Schweizer Bürgerin, Heirat mit der Landsfrau weniger als drei Wochen nach der Scheidung) zu vertuschen, nachdem die Fremdenpolizeibehörden weitere Abklärungen vorgenommen hatten und der Beschwerdeführer unter anderem die erste Heirat mit seiner heutigen Ehegattin verschwiegen hatte.
Was der Beschwerdeführer dagegen vorbringt, ist nicht geeignet, den Schluss der Vorinstanz, es liege eine Scheinehe vor, zu erschüttern. Entgegen der Behauptung des Beschwerdeführers hat die Vorinstanz gerade nicht gestützt auf einen einzelnen Hinweis, sondern aufgrund der Gesamtbetrachtung aller Indizien auf das Vorliegen einer Ausländerrechtsehe geschlossen. Selbst wenn aber - wie der Beschwerdeführer meint - vorliegend nicht von einer Scheinehe auszugehen wäre, vermöchte dies nichts daran zu ändern, dass der Beschwerdeführer wissentlich wesentliche Tatsachen verschwiegen hat, um sich ein Anwesenheitsrecht in der Schweiz zu verschaffen. Die Ehe mit der schweizerischen Ehefrau bestand jedenfalls schon lange vor Erteilung der Niederlassungsbewilligung nur formell und wurde vom Beschwerdeführer aufrecht erhalten zum alleinigen Zweck, die Erteilung der Niederlassungsbewilligung zu erwirken. Er beabsichtigte keineswegs, diese Ehe weiterzuführen, und hat die Behörden diesbezüglich jahrelang gezielt getäuscht. Hätten die Fremdenpolizeibehörden von seinen tatsächlichen familiären Verhältnissen und seinen Plänen Kenntnis gehabt, wäre dem Beschwerdeführer die Niederlassungsbewilligung nicht erteilt worden. Die Voraussetzungen für den Widerruf der Niederlassungsbewilligung des Beschwerdeführers sind somit so oder anders offensichtlich erfüllt.
2.6 Nicht durchzudringen vermag die Rüge, die Vorinstanz habe den Anspruch auf rechtliches Gehör verletzt, indem sie die ehemalige (schweizerische) Ehefrau nicht erneut als Zeugin einvernommen hat. Zwar umfasst der in Art. 29 Abs. 2 BV 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. 5.1 S. 293 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 f.; je mit Hinweisen). Diese Voraussetzungen waren vorliegend ohne weiteres erfüllt, weshalb von einer Gehörsverletzung nicht die Rede sein kann.
2.7 Weiter wirft der Beschwerdeführer der Vorinstanz mehrfach vor, sie habe eine willkürliche, Art. 9 BV verletzende Würdigung der Akten- und Beweislage vorgenommen und Art. 29 Abs. 2 BV verletzt, indem sie in unsachgemässer, unhaltbarer Art und Weise die Akten nur ausschnittartig gewürdigt habe.
Die Verletzung von Grundrechten prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG). Für derartige Rügen gelten die gleichen Begründungsanforderungen, wie sie gestützt auf Art. 90 Abs. 1 lit. b OG für die staatsrechtliche Beschwerde gegolten haben (<ref-ruling> E. 2.2 S. 246 mit Hinweis). Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen; auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.3 S. 261 mit Hinweisen). Was der Beschwerdeführer den Ausführungen der Vorinstanz entgegenhält, erschöpft sich darin, in appellatorischer Form seine eigene Sicht der Dinge vorzutragen. Auf die Beschwerde kann insoweit nicht eingetreten werden.
3. Der Widerruf der Niederlassungsbewilligung erweist sich vorliegend auch als verhältnismässig. Zwar scheint der Beschwerdeführer zumindest beruflich integriert zu sein. Von einer eigentlichen Verwurzelung in der Schweiz kann jedoch nicht gesprochen werden. Der Beschwerdeführer lebte bis zum 31. Altersjahr in seiner Heimat und hat damit die prägenden Lebensjahre in Mazedonien verbracht. Er hält sich erst seit dem Jahr 2000 in der Schweiz auf, wobei sein Aufenthalt zudem auf der Irreführung der Fremdenpolizei beruht. Es darf davon ausgegangen werden, dass er mit den kulturellen und gesellschaftlichen Gepflogenheiten seines Heimatlandes nach wie vor bestens vertraut ist. Ins Gewicht fällt zudem, dass seine heutige Ehefrau und die gemeinsamen Kinder sowie weitere Verwandte dort leben. Dem Beschwerdeführer ist somit zuzumuten, in seine Heimat zurückzukehren.
4. 4.1 Aufgrund des Gesagten ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Der Antrag, die Sache zur Festlegung einer Parteientschädigung an die kantonalen Instanzen zurückzuweisen, wird damit gegenstandslos.
4.2 Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig (Art. 65 und Art. 66 BGG).

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, 25. Februar 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Müller Dubs