Sachverhalt:
A. Der kosovarische Staatsangehörige X._ (geb. 5. November 1969) heiratete am 2. Juli 1990 im Heimatland die Landsfrau Y._ (geb. 23. April 1971). Aus dieser Ehe ging am 19. Juli 1991 der Sohn A._ hervor.
Die Ehe wurde am 30. November 1994 geschieden. Am 9. Dezember 1996 reiste X._ in die Schweiz ein und heiratete gleichentags eine 14 Jahre ältere Schweizer Bürgerin. Gestützt auf die Heirat wurde ihm eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau erteilt. In der Folge gebar ihm seine ehemalige Ehefrau zwei weitere Kinder, B._ (geb. 17. September 1998) und C._ (geb. 1. November 2000). Am 5. Dezember 2001 wurde X._ die Niederlassungsbewilligung erteilt. Die kinderlos gebliebene Ehe mit der schweizerischen Ehefrau wurde am 6. Juli 2005 geschieden.
Am 6. Dezember 2005 heirateten X._ und Y._ ein zweites Mal im Kosovo, worauf Y._ am 8. August 2006 in die Schweiz einreiste und am 12. September 2006 die Aufenthaltsbewilligung zum Verbleib bei ihrem Ehemann (letztmals verlängert bis zum 7. August 2008) erhielt.
Am 13. November 2006 bzw. am 20. September 2007 stellten Y._ und X._ ein Familiennachzugsgesuch für ihre drei Kinder. Darauf stellte ihnen das Migrationsamt des Kantons Zürich am 10. Dezember 2007 den Widerruf der Niederlassungs- bzw. der Aufenthaltsbewilligung in Aussicht und gewährte ihnen das rechtliche Gehör.
B. Mit Verfügung vom 12. März 2008 widerrief das Migrationsamt die Niederlassungsbewilligung von X._ sowie die Aufenthaltsbewilligung von Y._ wegen Verschweigens wesentlicher Tatsachen und setzte ihnen Frist zur Ausreise. Gleichzeitig wies es das Gesuch um Nachzug der drei Kinder ab.
X._ und Y._ erhoben dagegen ohne Erfolg vorerst Rekurs an den Regierungsrat des Kantons Zürich und sodann Beschwerde an das Verwaltungsgericht des Kantons Zürich.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 6. November 2009 beantragen X._ und Y._, den Entscheid des Verwaltungsgerichts des Kantons Zürich vom 26. August 2009 aufzuheben, die Aufenthalts- und Niederlassungsbewilligung der Beschwerdeführer nicht zu widerrufen, eventualiter die Sache zur Durchführung eines Beweisverfahrens zwecks Feststellung des Sachverhalts an die Vorinstanz zurückzuweisen. Zudem stellen sie das Begehren, der Beschwerde die aufschiebende Wirkung zu erteilen.
Das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten ist. Die Staatskanzlei des Kantons Zürich, im Auftrag des Regierungsrates, und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
D. Mit Verfügung vom 10. November 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 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. Vorliegend ist jedoch noch das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG) massgebend (Art. 126 Abs. 1 AuG analog).
1.2 Gegen kantonal letztinstanzliche Entscheide über den Widerruf von Niederlassungsbewilligungen 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).
Die Aufenthaltsbewilligung der Beschwerdeführerin 2 (Ehegattin) ist abgelaufen, weshalb deren Widerruf nicht mehr zur Diskussion steht. Nach Art. 17 Abs. 2 ANAG hat die Beschwerdeführerin 2 Anspruch auf Verlängerung ihrer Aufenthaltsbewilligung unter der Voraussetzung, dass der Beschwerdeführer 1 (Ehegatte) über die Niederlassungsbewilligung verfügt. Die Zulässigkeit der Beschwerde betreffend die Aufenthaltsbewilligung der Ehefrau hängt folglich davon ab, ob der Widerruf der Niederlassungsbewilligung des Beschwerdeführers 1 aufgehoben wird und dieser damit im Besitze der Niederlassungsbewilligung bleibt.
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (vgl. <ref-ruling> E. 1.4 S. 400). Hinsichtlich der Verletzung von Grundrechten gilt indessen eine qualifizierte Rügepflicht (Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.2 S. 254).
1.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, wie ihn die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Es kann diesen bloss berichtigen oder ergänzen, wenn er offensichtlich unrichtig, unvollständig oder in Verletzung wesentlicher Verfahrensrechte ermittelt wurde (Art. 105 Abs. 2 BGG). Der Betroffene hat darzulegen, dass und inwiefern dies klar und eindeutig der Fall ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3, 393 E. 7.1, 462 E. 2.4). Eine entsprechende Rüge setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweist (Art. 97 Abs. 1 BGG).
2. 2.1 Nach Art. 7 Abs. 1 ANAG (gültig bis 31. Dezember 2007) hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung; 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). 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). 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 Nach Art. 9 Abs. 4 lit. a ANAG kann eine Niederlassungsbewilligung widerrufen werden, wenn der Ausländer sie durch falsche Angaben oder wissentliches Verschweigen wesentlicher Tatsachen erschlichen hat. 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 (Urteile des Bundesgerichts 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.). Nach 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 (Urteile 2A.511/2001 vom 10. Juni 2002, publ. in: Pra 2002 Nr. 163, E. 3.2; 2A.57/2002 vom 20. Juni 2002, publ. in: Pra 2002 Nr. 165, E. 2.2, je mit Hinweisen). 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 Erteilung der Aufenthaltsbewilligung 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 (Urteil 2A.511/2001 vom 10. Juni 2002 E. 3.2).
2.3 Das Verwaltungsgericht geht in seinem Entscheid von der dargestellten Rechtsprechung aus und hat diese korrekt angewandt.
Der Beschwerdeführer liess sich von seiner Ehefrau, mit der er damals bereits ein gemeinsames Kind hatte, im Heimatland scheiden. Am Tag seiner Einreise in die Schweiz heiratete er eine 14 Jahre ältere Schweizer Bürgerin, die er angeblich während eines Ferienaufenthalts in der Schweiz kennen gelernt hatte. Während dieser Ehe führte er eine eheähnliche Beziehung mit seiner früheren Ehefrau im Heimatland fort, wobei er auch am gleichen Wohnort amtlich registriert blieb. Aus dieser Parallelbeziehung gingen zwei weitere Kinder (geb.1998 bzw. 2000) hervor, deren Geburt er gegenüber den schweizerischen Behörden verschwieg. Am 5. Dezember 2001 wurde dem Beschwerdeführer die Niederlassungsbewilligung erteilt. Nur einige Monate nach der Scheidung von der schweizerischen Ehefrau heiratete der Beschwerdeführer 1 am 6. Dezember 2005 seine frühere Ehefrau im Kosovo zum zweiten Mal und zog sie in die Schweiz nach, bevor in der Folge auch um Nachzug der drei gemeinsamen Kinder ersucht wurde. Hinweise darauf, dass die Feststellungen des Verwaltungsgerichts des Kantons Zürich zum Sachverhalt offensichtlich unrichtig wären, sind nicht ersichtlich und gehen namentlich auch nicht aus den Vorbringen der Beschwerdeführer hervor. Zusätzliche Sachverhaltsfeststellungen sind daher nicht erforderlich.
Aus dem zeitlichen Ablauf der Ereignisse ergibt sich eindeutig, dass der Beschwerdeführer nach einem aus zahlreichen Verfahren bekannten Verhaltensmuster (vgl. dazu etwa Urteile 2C_559/2009 vom 11. Februar 2010; 2C_311/2009 vom 5. Januar 2010; 2C_33/2008 vom 7. Mai 2008 mit Hinweisen) planmässig vorgegangen ist, um sich in der Schweiz ein Anwesenheitsrecht zu verschaffen und seiner Familie den Nachzug zu ermöglichen. Ob eine Scheinehe vorliegt, kann trotz zahlreicher Indizien dahingestellt bleiben. Jedenfalls bestand die Ehe mit der schweizerischen Ehefrau schon lange vor Erteilung der Niederlassungsbewilligung nur formell und wurde vom Beschwerdeführer aufrecht erhalten zum alleinigen Zweck, die Erteilung der Niederlassungsbewilligung zu erwirken. Seine Aussage, er habe die Geburt der Kinder den schweizerischen Behörden verschwiegen, um die Liebesbeziehung zur schweizerischen Ehefrau zu bewahren, ist unter den vorliegenden Umständen als reine Schutzbehauptung zu werten. Er beabsichtigte keineswegs, diese Ehe weiterzuführen, und hat die Behörden diesbezüglich jahrelang gezielt getäuscht. Ob die verschwiegene ausserehelichen Vaterschaft für sich allein zum Entzug der Aufenthaltsbewilligung geführt hätte, ist nicht entscheidend. Durch die Bekanntgabe der Existenz der beiden ausserehelichen Kinder hätte sich die Ausländerbehörde jedenfalls veranlasst gesehen bzw. sehen müssen, die Beziehung der Ehegatten näher zu überprüfen, womit ihr die effektiven ehelichen Umstände bekannt geworden wären. Hätten die Fremdenpolizeibehörden von seinen tatsächlichen familiären Verhältnissen und seinen Plänen Kenntnis gehabt, wäre dem Beschwerdeführer 1 die Niederlassungsbewilligung nicht erteilt worden. Zusammenfassend ergibt sich, dass der Beschwerdeführer den Tatbestand des Erschleichens der Niederlassungsbewilligung und damit den Widerrufsgrund gemäss Art. 9 Abs. 4 lit. a ANAG erfüllt. Was die Beschwerdeführer dagegen einwenden, vermag diese Würdigung nicht zu erschüttern. Zur Begründung kann ergänzend auf die Ausführungen im angefochtenen Entscheid verwiesen werden.
2.4 Nicht durchzudringen vermag die Rüge, die Vorinstanz habe den Anspruch auf rechtliches Gehör verletzt, indem sie verschiedene Zeugen nicht einvernommen habe. 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 sind vorliegend erfüllt. Die Vorinstanz durfte ohne weiteres davon ausgehen, dass die Anhörung der Verwandten des Beschwerdeführers 1 zu keinen neuen Erkenntnissen führen würde. Allfällige Aussagen der ehemaligen Ehegattin konnten für den hier zu beurteilenden Sachverhalt zum Vornherein nicht entscheidend sein. Ob der Beschwerdeführer 1 eine Scheinehe eingegangen war, liess die Vorinstanz zudem ausdrücklich offen, weshalb sich die Anhörung der ehemaligen schweizerischen Ehegattin auch insofern erübrigte. Von einer Verletzung des rechtlichen Gehörs kann somit nicht die Rede sein. Auf die Rüge, die Vorinstanz habe "diverse" Beweismittel nicht geprüft, wobei diese in der Beschwerdeschrift nicht näher bezeichnet werden, kann mangels genügender Begründung nicht eingetreten werden (vgl. E. 1.3).
2.5 Der Widerruf der Niederlassungsbewilligung erweist sich vorliegend auch als verhältnismässig. Zwar scheint der Beschwerdeführer 1 zumindest beruflich integriert zu sein. Von einer eigentlichen Verwurzelung in der Schweiz kann jedoch nicht gesprochen werden. Bis zum 27. Altersjahr lebte er in seiner Heimat und hat damit dort die prägenden Lebensjahre verbracht. Er hält sich allerdings seit dem Jahr 1996 in der Schweiz auf; diese relativ lange Aufenthaltsdauer wird aber insofern relativiert, als seine Anwesenheit auf der Irreführung der Fremdenpolizei beruht. Weiter 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 die drei Kinder sowie weitere Verwandte dort leben. Dem Beschwerdeführer 1 ist somit zuzumuten, zusammen mit seiner Ehefrau und Mutter der Kinder in die gemeinsame Heimat zurückzukehren.
3. Der verfügte Widerruf der Niederlassungsbewilligung verletzt somit weder Bundesrecht noch Art. 8 EMRK. Ist die Niederlassungsbewilligung des Beschwerdeführers 1 jedoch widerrufen, verfügen die Beschwerdeführer weder gestützt auf Bundesrecht noch aufgrund staatsvertraglicher Bestimmungen über einen Bewilligungsanspruch. Soweit sich die Beschwerde sinngemäss gegen die Nichtverlängerung der Aufenthaltsbewilligung der Beschwerdeführerin 2 richtet, kann darauf nicht eingetreten werden (Art. 83 lit. c Ziff. 2 BGG). Fehlt ein Anwesenheitsanspruch, steht die Erteilung einer Aufenthaltsbewilligung nach Art. 4 ANAG im freien Ermessen der Behörden. Diesbezüglich ist jedoch die Beschwerde ans Bundesgericht ausgeschlossen.
4. 4.1 Aufgrund des Gesagten erweist sich die Beschwerde als unbegründet. Sie ist abzuweisen, soweit darauf eingetreten werden kann.
4.2 Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (Art. 65, Art. 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 19. April 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Zünd Dubs