Sachverhalt:
A. X._ (geb. 1969) ist Staatsangehöriger der Republik Kosovo (vormals Serbien und Montenegro). Er heiratete 1989 in der gemeinsamen Heimat die Landsfrau Y._. Aus dieser Ehe gingen die Kinder A._ (geb. 1992) und B._ (geb. 1995) hervor. Die Ehe wurde am 21. November 1996 im Kosovo geschieden und das Sorgerecht dem Vater zugesprochen. Am 11. Dezember 1996 reiste dieser alleine in die Schweiz und ersuchte um Asyl. Mit Verfügung vom 9. April 1997 wies das damalige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) das Gesuch ab und setzte X._ eine Ausreisefrist bis zum 31. August 1997. Diese Anordnung erwuchs in Rechtskraft.
Am 27. August 1997 meldeten X._ und die Schweizer Bürgerin Z._ (geb. 1965), welche ursprünglich aus der Dominikanischen Republik stammt, das Eheversprechen an; die Trauung erfolgte am 17. Oktober 1997. In der Folge wurde X._ die Aufenthaltsbewilligung zum Verbleib bei der schweizerischen Ehefrau und nach fünf Jahren Ehedauer am 27. September 2002 die Niederlassungsbewilligung für den Kanton Zürich erteilt. Am 30. Juni 2004 wurde die Ehe X._ - Z._ auf gemeinsames Begehren vom Bezirksgericht Pfäffikon/ZH rechtskräftig geschieden.
B. Am 5. Januar 2006 heiratete X._ in seiner Heimat erneut seine frühere Ehefrau Y._. Am 10. März 2006 stellte er beim Migrationsamt des Kantons Zürich das Gesuch um Familiennachzug für seine Ehefrau und die beiden Kinder.
Am 15. Dezember 2006 widerrief das Migrationsamt die Niederlassungsbewilligung von X._ und lehnte gleichzeitig die Gesuche um Bewilligung der Einreise seiner Ehefrau und Kinder ab.
Dagegen erhob X._ 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 14. Mai 2009 an das Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts vom 25. März 2009 und der Widerruf der Niederlassungsbewilligung seien aufzuheben. Eventualiter sei dem Beschwerdeführer die Aufenthaltsbewilligung zu erteilen. Gerügt wird die Verletzung von Art. 9 Abs. 4 lit. a (und Art. 7 Abs. 2) ANAG, die Verletzung des rechtlichen Gehörs (<ref-law>) sowie eine offensichtlich unrichtige Sachverhaltsfeststellung.
D. Der Regierungsrat und das Verwaltungsgericht des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
E. Mit verfahrensleitender Verfügung vom 18. Mai 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Nach <ref-law> 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. Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121; in Kraft gewesen bis 31. Dezember 2007), das hier unbestrittenermassen noch anwendbar ist (vgl. Art. 126 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20]), entscheiden die zuständigen Behörden, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung einer entsprechenden Bewilligung, es sei denn, der Ausländer oder seine in der Schweiz lebenden Angehörigen könnten sich auf eine Sondernorm des Bundesrechts (einschliesslich Bundesverfassungsrecht) oder eines Staatsvertrages berufen (<ref-ruling> E. 1.1 S. 3 f. mit Hinweisen).
1.2 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 grundsätzlich eingetreten werden (vgl. jedoch E. 1.3 hiernach).
1.3 Nicht zulässig ist das erhobene Rechtsmittel dagegen insoweit, als der Beschwerdeführer eventualiter - für den Fall, dass der Widerruf der Niederlassungsbewilligung geschützt wird - beantragt, es sei ihm eine Aufenthaltsbewilligung zu erteilen. Diesbezüglich fehlt es an einem Rechtsanspruch auf Bewilligungserteilung (Urteil 2C_72/2009 vom 5. März 2009 E. 1.3). Der Beschwerdeführer macht denn auch nicht konkret geltend, sein verfassungsmässiger Anspruch auf Schutz des Familienlebens wäre verletzt; der vom Beschwerdeführer angerufene <ref-law> vermag hier keinen Bewilligungsanspruch zu begründen. Im Umfang des Eventualantrags kann daher auf die eingereichte Beschwerde nicht eingetreten werden.
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (<ref-law>), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweist (<ref-law>).
2. 2.1 Gemäss Art. 7 Abs. 1 ANAG 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. Kein Anspruch besteht, 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 (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. 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. 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_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, in: Uebersax/Münch/Geiser/Arnold, Ausländerrecht, 2002, Rz. 6.16).
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.4 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).
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 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 (<ref-ruling> E. 4a S. 55 mit Hinweisen; Urteil 2C_446/2009 vom 23. November 2009 E. 2.2).
2.4 Die Vorinstanz hat diese Rechtsprechung nicht verkannt und sie im konkreten Fall korrekt angewandt: Der Beschwerdeführer erhielt die Niederlassungsbewilligung wegen der fünf Jahre dauernden Ehe mit der vier Jahre älteren, eingebürgerten zweiten Ehefrau. Die erste Ehe war am 21. November 1996 geschieden worden; bereits am 11. Dezember 2006 reiste der Beschwerdeführer als Asylbewerber in die Schweiz ein, wo er nach ungefähr acht Monaten, nur vier Tage bevor er die Schweiz nach abgelehntem Asylgesuch wieder hätte verlassen müssen, erneut heiratete. Die Eheleute bewohnten gemäss den verbindlichen Feststellungen der Vorinstanz während ihrer 63⁄4 Jahre dauernden Ehe nur einmal und während kurzer Zeit gegen das Ende ihrer Ehe eine 21⁄2 -Zimmer-Wohnung. Während der übrigen Zeit teilten sie sich ein Zimmer bzw. mehrere 1-Zimmer-Wohnungen. Die Ehefrau wohnte während eines grossen Teils der Zeit auswärts, wo sie ihrem Beruf als erotische Masseuse nachging. Die Eheleute wussten wenig über ihre gegenseitigen Verwandten und Familien und verbrachten nie gemeinsame Ferien. Gemäss der Vorinstanz handelt es sich um eine "Ehe mit wenig Gemeinsamkeiten, wenig Kommunikation und minimaler Anteilnahme am Alltag des Partners und seiner Angehörigen".
Die Vorinstanz durfte insbesondere auch aus dem Umstand, dass der Beschwerdeführer mehrere Wochen im Jahr allein bei seiner früheren Familie verbrachte, den Schluss ziehen, dass neben der Beziehung zu seinen Kindern auch diejenige zu seiner heutigen (und ersten) Ehefrau aufrecht erhalten wurde. Die Ehefrau kehrte denn auch nach der Scheidung nicht zu ihrer Familie zurück, sondern behielt die Betreuung der Kinder am Wohnsitz der Eltern des von ihr geschiedenen Beschwerdeführers im Kosovo bei.
Nachdem der Beschwerdeführer die Niederlassungsbewilligung erhalten hatte, wurde die zweite Ehe - etwa eindreiviertel Jahre später - geschieden. Eineinhalb Jahre nach der Scheidung heiratete der Beschwerdeführer seine erste Ehefrau, und weitere zwei Monate später stellte er das Gesuch um Nachzug seiner Familie in die Schweiz.
2.5 Die in der Beschwerdeschrift zahlreich erhobenen Sachverhaltsrügen bezüglich der ehelichen Beziehungen erscheinen nicht stichhaltig. Es wird nicht substantiiert dargetan, inwiefern die Sachverhaltsdarstellung im angefochtenen Urteil offensichtlich falsch oder unrichtig sein sollte. Die Vorinstanz hat den entscheidrelevanten Sachverhalt nicht wie behauptet "voreingenommen" festgestellt.
Vielmehr durfte die Vorinstanz annehmen, die oben in E. 2.4 dargestellten Umstände belegten, dass der Beschwerdeführer rechtsmissbräuchlich an der zweiten Ehe festgehalten hat, um die Niederlassungsbewilligung zu erhalten. Wird eine solche dergestalt erschlichen, so kann sie in der Folge auch widerrufen werden. Der angefochtene Entscheid verletzt somit Bundesrecht nicht.
2.6 Nicht durchzudringen vermag auch die Rüge, die Vorinstanzen hätten den Anspruch auf rechtliches Gehör verletzt, indem sie die von den Beschwerdeführern beantragten Einvernahmen von Personen aus deren Bekanntenkreis bzw. die nochmalige Einvernahme der ehemaligen (schweizerischen) Ehefrau in Anwesenheit des Beschwerdeführers ablehnten. Zwar umfasst der in <ref-law> 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. 3a S. 51 und 241 E. 2 S. 242; je 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). Inwiefern die Aussagen von aussenstehenden Drittpersonen geeignet wären, im vorliegenden Fall einen besseren Eindruck von den tatsächlichen Absichten des Beschwerdeführers bzw. von inneren Tatsachen wie etwa dem Ehewillen zu vermitteln, ist nicht ersichtlich. Dies umso weniger, als die Personen, welche um Abgabe derartiger Auskünfte gebeten werden, den ersuchenden Personen gegenüber in aller Regel wohlwollend eingestellt sind und beabsichtigen, diesen zu helfen. Dass das Verwaltungsgericht in dieser Situation auf die beantragten Einvernahmen verzichtet hat, ist daher nachvollziehbar und stellt jedenfalls keine Verletzung von <ref-law> dar.
Zudem steht der Behörde - wie selbst der Beschwerdeführer einräumt - bei der Beurteilung der Frage, ob hinreichende Gründe bestehen, um eine Partei ausnahmsweise von der Anhörung der Auskunftsperson auszuschliessen, ein Ermessensspielraum zu (<ref-ruling> E. 2.3.5 S. 174). Inwiefern hier ein Ermessensmissbrauch vorliegen soll, ist nicht ersichtlich.
2.7 Der Widerruf der Niederlassungsbewilligung ist unter den gegebenen Umständen auch 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 27. Altersjahr in seiner Heimat und hat damit die prägenden Lebensjahre im Kosovo verbracht. 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 beiden Kinder sowie seine weiteren Verwandten dort leben; daran vermag auch der Einwand nichts zu ändern, dass offenbar die Ehefrau des Beschwerdeführers im Kosovo in der Zwischenzeit die Scheidung verlangt. Dem Beschwerdeführer ist somit zuzumuten, in seine Heimat zurückzukehren.
3. 3.1 Der verfügte Widerruf der Niederlassungsbewilligung erweist sich als bundesrechtskonform. Die Beschwerde ist somit als unbegründet abzuweisen, soweit darauf eingetreten werden kann.
3.2 Bei diesem Verfahrensausgang wird der Beschwerdeführer kostenpflichtig (<ref-law>). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

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, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 5. Januar 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger