Sachverhalt: A. Der aus dem Kosovo stammende A.X._ (geb. 1969) reiste erstmals 1990 illegal in die Schweiz ein. Am 6. Januar 1993 wurde er im Rahmen der "Aktion Jugoslawien" (Bundesratsbeschluss vom 18. Dezember 1991) vorläufig aufgenommen. Am 23. August 2002 erhielt er die Niederlassungsbewilligung im Kanton Zürich. Zwei Monate später und sodann nochmals am 30. September 2003 ersuchte er um Bewilligung des Nachzugs seiner drei Kinder B.X._,C.X._ und D.X._ (geb. 1994, 1996 und 1998), welche die gleiche Staatsangehörigkeit besitzen wie er. Das Migrationsamt des Kantons Zürich (im Folgenden: Migrationsamt) verweigerte am 26. Mai 2005 den Nachzug der Kinder und widerrief die Niederlassungsbewilligung des Vaters. Den dagegen erhobenen Rekurs hiess der Regierungsrat des Kantons Zürich am 14. Dezember 2005 insoweit gut, als er den Widerruf der Niederlassungsbewilligung für ungültig erklärte und das Migrationsamt anwies, über das Familiennachzugsgesuch neu zu entscheiden. Nach weiteren Sachverhaltsabklärungen wies das Migrationsamt das Nachzugsbegehren am 13. Juni 2006 wiederum ab. Die hiegegen im Kanton zunächst beim Regierungsrat und anschliessend beim Verwaltungsgericht erhobenen Rechtsmittel blieben erfolglos. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. November 2009 beantragen A.X._ und seine drei Kinder dem Bundesgericht, den in dieser Sache zuletzt ergangenen Entscheid des Verwaltungsgerichts vom 26. August 2009 aufzuheben und das Migrationsamt anzuweisen, den Kindern die Einreise sowie die Anwesenheit in der Schweiz zu bewilligen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht stellt den Antrag, die Beschwerde abzuweisen, soweit auf sie einzutreten ist. Der Regierungsrat, vertreten durch seine Staatskanzlei, sowie das Bundesamt für Migration beantragen Abweisung der Beschwerde. Das Migrationsamt hat sich nicht vernehmen lassen.