Sachverhalt:
A. Der aus dem Kosovo stammende A._, geb. 1971, heiratete im Oktober 2002 in seiner Heimat die gleichaltrige französische Staatsangehörige D._. Im Dezember 2003 zog er mit einer Aufenthaltsbewilligung EG/EFTA zu seiner im Kanton Neuenburg lebenden Ehefrau. Im April 2004 nahm A._ Wohnsitz im Kanton Zürich, wo er erneut eine Aufenthaltsbewilligung EG/EFTA erhielt, die später bis zum Juli 2012 verlängert wurde.
B. Am 30. August 2007 ersuchten A._ und seine Ehefrau um Einreise- und Aufenthaltsbewilligung im Familiennachzug für die im Kosovo lebenden Kinder B._, geb. 1995, und C._, geb. 1998. Die Kinder stammen aus der Beziehung des damals unverheirateten A._ mit einer ebenfalls im Kosovo lebenden Landsfrau. Mit Verfügung vom 11. Dezember 2007 verweigerte die Sicherheitsdirektion (Migrationsamt) des Kantons Zürich den Nachzug der Kinder.
C. Am 13. August 2008 wies der Regierungsrat des Kantons Zürich einen dagegen gerichteten Rekurs im Wesentlichen ab. Mit Urteil vom 4. März 2009 wies das Verwaltungsgericht des Kantons Zürich, 4. Kammer, eine dagegen erhobene Beschwerde ebenfalls ab. Dem Urteil des Verwaltungsgerichts ist die abweichende Meinung einer Minderheit der Kammer sowie der Gerichtssekretärin beigeheftet.
D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht stellen A._ und seine Kinder B._ und C._ die folgenden Anträge:
"1. Die Beschwerde sei gutzuheissen, der Entscheid der 4. Kammer der 4. Abteilung des Verwaltungsgerichts des Kantons Zürich vom 4.3.2009 vollumfänglich aufzuheben und
1.1 In der Hauptsache den 2. und 3. Beschwerdeführern zu bewilligen, in die Schweiz einzureisen, um beim 1. Beschwerdeführer verbleiben zu können;
1.2 Im Kostenpunkt die Sache mit der Weisung an die Vorinstanz zurückzuweisen, ... die Kosten für das Verfahren vor der Sicherheitsdirektion des Kantons Zürich, für das Rekursverfahren vor dem Regierungsrat des Kantons Zürich sowie für das Verwaltungsgerichtsbeschwerdeverfahren vor ihr neu zu verlegen.
2. Eventuell sei die Beschwerde gutzuheissen, der Entscheid der 4. Kammer der 4. Abteilung des Verwaltungsgerichtes des Kantons Zürich vom 4.3.2009 vollumfänglich aufzuheben und die Sache mit der Weisung an die Vorinstanz (Verwaltungsgericht des Kantons Zürich) zurückzuweisen, ... neu zu entscheiden.
..."
E. Die Staatskanzlei des Kantons Zürich hat für den Regierungsrat des Kantons Zürich auf eine Vernehmlassung verzichtet. Das Verwaltungsgericht des Kantons Zürich hat sich in zwei Punkten zur Beschwerde geäussert, ohne formell Antrag zu stellen. Das Bundesamt für Migration reichte seine Stellungnahme nach Ablauf der ihm angesetzten Frist ein.
Erwägungen:
1. 1.1 Nach Art. 83 lit. c Ziff. 1 und 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig gegen Entscheide auf dem Gebiet des Ausländerrechts über Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
1.2 Am 1. Januar 2008 ist das Bundesgesetz über die Ausländerinnen und Ausländer vom 16. Dezember 2005 (AuG; SR 142.20) in Kraft getreten. Nach Art. 126 AuG bleibt das alte Recht (Bundesgesetz vom 26. Mai 1931 über Aufenthalt und Niederlassung der Ausländer [ANAG] und Ausführungserlasse) anwendbar auf Gesuche, die vor dem Inkrafttreten des neuen Gesetzes eingereicht worden sind. Das Verfahren richtet sich jedoch nach dem neuen Recht. Im vorliegenden Verfahren ist in materiell-rechtlicher Hinsicht auf das alte Recht abzustellen, da das Bewilligungsgesuch noch vor dem 1. Januar 2008 eingereicht wurde (BGE 135 I 142 E. 1.2 S. 145).
1.3 Die Ehefrau des Beschwerdeführers 1 ist französische Staatsangehörige und hat damit gestützt auf das Freizügigkeitsrecht (Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit, FZA; SR 0.142.112.681) ein Recht auf Aufenthalt in der Schweiz. Als ihr Ehemann hat auch der Beschwerdeführer selbst in Anwendung von Art. 7 lit. d FZA und Art. 3 Abs. 2 lit. a Anhang I FZA ein Recht auf Aufenthalt in der Schweiz. Ob die Kinder, um deren Nachzug es hier geht, ebenfalls über einen solchen Anspruch verfügen, ist strittig. Unabhängig davon können sich die Beschwerdeführer aber jedenfalls auf Art. 8 EMRK bzw. Art. 13 BV berufen, da der Beschwerdeführer 1 einen Anspruch auf Anwesenheitsbewilligung und damit ein gefestigtes Anwesenheitsrecht hat, sofern die familiäre Beziehung zwischen ihm und seinen Kindern intakt ist und tatsächlich gelebt wird (vgl. BGE 135 I 143 E. 1.3.1 S. 145 f. mit Hinweis), was von keiner Seite bestritten wird. Bereits aus diesem Grund ist auf die Beschwerde einzutreten. Es rechtfertigt sich daher, auf die Frage der Anwendbarkeit des Freizügigkeitsrechts einzig unter materiellen Gesichtspunkten einzugehen.
1.4 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht - inklusive Bundesverfassungsrecht -, Völkerrecht sowie kantonale verfassungsmässige Rechte (Art. 95 BGG). Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG). Dazu zählt auch die unvollständige Feststellung rechtserheblicher Tatsachen (vgl. BGE 133 IV 293 E. 3.4.2 S. 295 f.).
1.5 Die Stellungnahme des Bundesamts für Migration wurde der Schweizerischen Post erst am 8. September 2009 und damit einen Tag nach Ablauf der dem Amt gesetzten Frist bis zum 7. September 2009 aufgegeben, weshalb sie als verspätet aus dem Recht zu weisen ist.
2. 2.1 Das Verwaltungsgericht des Kantons Zürich geht davon aus, die Beschwerdeführer könnten sich nicht auf das Freizügigkeitsrecht berufen bzw. hätten gestützt auf das Freizügigkeitsabkommen keinen Anspruch auf Erteilung einer Aufenthaltsbewilligung an die vorehelichen Kinder des Beschwerdeführers 1.
2.2 Nach Art. 7 lit. d FZA regelt das Freizügigkeitsabkommen unter anderem das Aufenthaltsrecht der Familienangehörigen der Staatsangehörigen der Vertragsstaaten, und zwar ungeachtet ihrer Staatsangehörigkeit. Gemäss Art. 3 Abs. 1 Anhang I FZA haben die Familienangehörigen einer Person, die Staatsangehörige einer Vertragspartei des Abkommens ist und ein Aufenthaltsrecht hat, das Recht, bei ihr Wohnung zu nehmen. Als Familienangehörige gelten insbesondere, ungeachtet ihrer Staatsangehörigkeit, der Ehegatte und die Verwandten in absteigender Linie, die noch nicht 21 Jahre alt sind oder denen Unterhalt gewährt wird, sowie die Verwandten und die Verwandten des Ehegatten in aufsteigender Linie, denen Unterhalt gewährt wird (vgl. Art. 3 Abs. 2 lit. a und b Anhang I FZA). Der Beschwerdeführer 1 ist nicht selbst EU-Bürger; er ist aber mit einer französischen Staatsangehörigen und damit einer Unionsbürgerin verheiratet, die in der Schweiz eine Anwesenheitsbewilligung hat. Gestützt auf Art. 3 Abs. 2 lit. a Anhang I FZA erhielt er denn auch aufgrund des ehelichen Verhältnisses eine Aufenthaltsbewilligung EG/EFTA.
2.3 Strittig ist hier, ob auch die ausländischen Kinder des Beschwerdeführers 1 aus einer vorehelichen Beziehung, die Beschwerdeführer 2 und 3, aus dem Freizügigkeitsabkommen ein Aufenthaltsrecht ableiten können. Die Vorinstanzen wenden dagegen ein, die Nachkommen des Ehegatten würden von Art. 3 Anhang I FZA nicht erfasst. Selbst wenn die Anwendbarkeit der Bestimmung grundsätzlich auf solche Verwandtschaftsverhältnisse ausgeweitet würde, fiele dies bei Drittausländern nur dann in Betracht, wenn die Stiefkinder sich vorher bereits rechtmässig in einem Staat der EG oder EFTA aufgehalten hätten; für einen Nachzug direkt aus dem Drittstaat vermittle das Freizügigkeitsabkommen keinen Anspruch. Die Vorinstanzen stützen sich dabei auf die bundesgerichtliche Rechtsprechung, wie sie in BGE 130 II 1 E. 3.6 S. 9 ff. und 134 II 10 E. 3 S. 14 ff. wiedergegeben wurde und die wiederum auf das Urteil i.S. Akrich des Gerichtshofs der Europäischen Gemeinschaften (EuGH) zurückging (C-109/01 vom 23. September 2003, Slg. 2003 S. I-9607).
2.4 Mit Urteil 2C_196/2009 vom 29. September 2009 (zur Publikation in der Amtlichen Sammlung bestimmt) schloss sich indessen das Bundesgericht einer Änderung der Rechtsprechung des EuGH an, die dieser mit seinem Urteil C-127/08 vom 25. Juli 2008 i.S. Metock vorgenommen hatte. Damit gab der EuGH seine im Urteil i.S. Akrich (C-109/01; vgl. vorne E. 2.3) begründete Rechtsprechung, wonach das Recht auf Familiennachzug von einem vorherigen rechtmässigen Aufenthalt in einem Mitgliedstaat abhing, wieder auf und erkannte, eine solche Voraussetzung verletze die gemeinschaftsrechtliche Regelung der Familienvereinigung. Das Bundesgericht erwog seinerseits unter anderem, bereits der Entscheid i.S. Akrich vom 23. September 2003 (C-109/01; vgl. vorne E. 2.3) sei erst nach der Unterzeichnung des Freizügigkeitsabkommens am 21. Juni 1999 gefällt worden, gehöre damit nicht zum damaligen freizügigkeitsrechtlichen Besitzstand und stelle daher für die Schweiz keine verbindliche Vorgabe dar (vgl. Art. 16 FZA sowie E. 3.1 hienach). Insbesondere zur Gewährleistung einer parallelen Rechtslage dränge es sich auf, auch die modifizierte Rechtsprechung des EuGH für das freizügigkeitsrechtliche Verhältnis zwischen der Schweiz und der EG und ihren Mitgliedstaaten zu übernehmen. Das Verwaltungsgericht kannte im Zeitpunkt, als es das angefochtene Urteil fällte, lediglich die neue Rechtsprechung des EuGH, konnte hingegen von der Praxisänderung des Bundesgerichts noch nichts wissen; unabhängig davon ist aber die damit als zutreffend erkannte Rechtslage auf den noch nicht rechtskräftig entschiedenen vorliegenden Fall anwendbar. Ein allfälliger Nachzug der Kinder des Beschwerdeführers 1 hängt mithin nicht davon ab, ob diese sich bereits rechtmässig in einem EG- oder EFTA-Staat aufhalten.
2.5 Zu prüfen bleibt freilich, ob auch Stiefkinder in den Anwendungsbereich von Art. 3 Anhang I FZA fallen.
3. 3.1 Für die Auslegung des Freizügigkeitsabkommens nicht massgeblich ist grundsätzlich die nationale Umsetzung des Freizügigkeitsrechts. Vielmehr ist das Freizügigkeitsrecht auf eigener Grundlage auszulegen (vgl. das erwähnte Urteil des Bundesgerichts 2C_196/2009 vom 29. September 2009 E. 3.6.1). Gemäss Art. 16 Abs. 2 FZA ist für die Anwendung des Freizügigkeitsabkommens die einschlägige Rechtsprechung des EuGH vor dem Zeitpunkt der Unterzeichnung (21. Juni 1999) massgebend. Das Bundesgericht kann aber, ohne dazu verpflichtet zu sein, zum Zwecke der Auslegung des Freizügigkeitsabkommens auch seither ergangene Urteile des Gerichtshofs heranziehen (BGE 130 II 1 E. 3.6.1 S. 10 f., 113 E. 5.2 S. 119 f.). Ziel ist, dass in den Beziehungen zwischen der Schweiz und der Europäischen Gemeinschaft gleichwertige Rechte und Pflichten wie in den Rechtsakten der Europäischen Gemeinschaft, auf die Bezug genommen wird, Anwendung finden (Art. 16 Abs. 1 FZA). Das bedeutet, dass für die vom Abkommen erfassten Bereiche insoweit eine parallele Rechtslage verwirklicht werden soll. Da der EuGH nicht berufen ist, für die Schweiz über die Auslegung des Abkommens verbindlich zu bestimmen, ist es dem Bundesgericht nicht verwehrt, aus triftigen Gründen zu einer anderen Rechtsauffassung als dieser zu gelangen. Es wird das aber mit Blick auf die angestrebte parallele Rechtslage nicht leichthin tun (vgl. das Urteil des Bundesgerichts 2C_196/2009 vom 29. September 2009 E. 3.4).
3.2 Gemäss dem deutschsprachigen Wortlaut von Art. 3 Abs. 2 Anhang I lit. a FZA zählen "der Ehegatte und die Verwandten in absteigender Linie", nach lit. b derselben Bestimmung "die Verwandten und die Verwandten des Ehegatten in aufsteigender Linie" zu den nachzugsberechtigten Familienangehörigen. Unklar ist, ob die Nachkommen des Ehegatten ebenfalls dazu gehören bzw. ob diese unter den Begriff der Verwandten in absteigender Linie nach lit. a fallen und deshalb im Übrigen nicht mehr ausdrücklich erwähnt werden oder ob es sich um einen bewussten Ausschluss vom Nachzugsrecht handelt. Einen ersten Hinweis dazu geben die französisch- und italienischsprachigen Fassungen des Freizügigkeitsabkommens, worin die Formulierungen "son conjoint et leurs descendants" bzw. "il coniuge e i loro discendenti" verwendet werden. Diese Wortlaute (insbes. "leurs" und "i loro") sprechen eher dafür, dass die Kinder beider Ehegatten gemeint sind.
3.3 Den Materialien des Freizügigkeitsabkommens lassen sich keine weiteren Anhaltspunkte entnehmen, wie Art. 3 Abs. 2 Anhang I FZA betreffend den Nachzug von Stiefkindern zu verstehen ist (BGE 130 II 1 E. 3.5 S. 9 mit verschiedenen Hinweisen wie insbes. auf BBl 1999 S. 6311). Lehre (vgl. Minh Son Nguyen, Droit public des étrangers, 2003, 395 f.) und Praxis (vgl. das Rundschreiben des Bundesamts für Ausländerfragen vom 8. Juli 2002 zu Grundsatzfragen bei der Umsetzung des Freizügigkeitsabkommens, Ziff. 2.1) sind freilich schon bei Einführung der Personenfreizügigkeit davon ausgegangen, erfasst seien sowohl die gemeinsamen Kinder der Ehegatten als auch einerseits diejenigen des Angehörigen des Vertragsstaates sowie andererseits diejenigen von dessen Ehepartner mit Drittstaatsangehörigkeit, und zwar von diesem adoptierte wie auch aus einer anderen Beziehung stammende Kinder.
3.4 In der Europäischen Union ist der Begriff des freien Personenverkehrs eng verknüpft mit demjenigen der Unionsbürgerschaft (vgl. heute Art. 20 ff. der konsolidierten Fassung des Vertrags über die Arbeitsweise der Europäischen Union vom 13. Dezember 2007 [Vertrag von Lissabon]; ABl. Nr. C 115 vom 9. Mai 2008, S. 47 ff.). Diese wurde durch den Vertrag von Maastricht vom 7. Februar 1992 (ABl. Nr. C 191 vom 29. Juli 1992, S. 1 ff.; vgl. Art. 17 ff. des EG-Vertrags in der damaligen Fassung) und damit vor Unterzeichnung des Freizügigkeitsabkommens eingeführt (Dieter W. Grossen/Claire de Coulon, Bilaterales Abkommen über die Freizügigkeit zwischen der Schweiz und der Europäischen Gemeinschaft und ihren Mitgliedstaaten, in: Thürer/Weber/Portmann/Kellerhals [Hrsg.], Bilaterale Verträge I & II Schweiz - EU, 2007, 181, Rz. 141). Beim Abschluss des Freizügigkeitsabkommens galt in der Europäischen Gemeinschaft die Verordnung (EWG) Nr. 1612/68 des Rates vom 15. Oktober 1968 über die Freizügigkeit der Arbeitnehmer innerhalb der Gemeinschaft (ABl. Nr. L 257 vom 19. Oktober 1968, S. 2 ff.), welche auch die massgeblichen Bestimmungen zur Familienvereinigung enthielt. Die entsprechende Regelung im Freizügigkeitsabkommen ist derjenigen der Verordnung Nr. 1612/68 nachgebildet. Am 17. September 2002 entschied der EuGH unter Anwendung dieser Verordnung, das Recht auf Wohnungsnahme beim Wanderarbeiter stehe sowohl den Nachkommen des Arbeitnehmers als auch denen seines Ehegatten zu (Urteil C-413/1999, Baumbast und R., Slg. 2002, I-7091, Randnr. 57). Der Gerichtshof stützte sich dabei unter anderem auf ein früheres Urteil vom 15. März 1989, mit dem er bereits entschieden hatte, die Verordnung 1612/68 sei mit Blick auf die Ziele der Freizügigkeit der Arbeitnehmer und deren Integration grundsätzlich weit auszulegen, ohne dass konkret über den Nachzug von Stiefkindern zu befinden war (Urteil C-389/87, Echternach G.B.C., Slg. 1989, 723). In einem weiteren Urteil vom 19. Oktober 2004 entschied der EuGH, dass es einem Elternteil mit Drittstaatsangehörigkeit, der für einen minderjährigen Unionsbürger sorgt, unter bestimmten Voraussetzungen (insbes. Vorhandensein genügender finanzieller Mittel) erlaubt ist, sich mit dem Kind im Aufnahmemitgliedstaat aufzuhalten (Urteil C-200/02, Zhu und Chen, Slg. 2004 S. I-9925). Dieses Urteil beruhte auf der Richtlinie 90/364/EWG des Rates vom 28. Juni 1990 über das Aufenthaltsrecht (ABl. Nr. L 180 vom 13. Juli 1990, S. 26) sowie auf Art. 18 des EG-Vertrags in der konsolidierten Fassung gemäss dem Vertrag von Amsterdam vom 2. Oktober 1997 (ABl. Nr. C 340 vom 10. November 1997, S. 173) bzw. des Vertrags von Nizza vom 10. März 2001 (ABl. Nr. C 80 vom 10. März 2003, S. 1).
3.5 Die Verordnung 1612/68 wurde inzwischen durch die Richtlinie 2004/38/EG des Europäischen Parlaments und des Rates vom 29. April 2004 über das Recht der Unionsbürger und ihrer Familienangehörigen, sich im Hoheitsgebiet der Mitgliedstaaten frei zu bewegen und aufzuhalten (ABl. Nr. L 158 vom 30. April 2004, S. 77, bzw. in berichtigter Fassung ABl. Nr. L 229 vom 29. Juni 2004, S. 35 ff.) abgeändert (dazu GROSSEN/DE COULON, a.a.O., 181 ff., Rz. 141 ff.). Darin ist nunmehr ausdrücklich festgehalten, dass zu den Verwandten in absteigender Linie auch diejenigen des Ehegatten zählen (Art. 2 Ziff. 2 lit. c RL 2004/38/EG).
3.6 Das Bundesgericht hat die Frage, ob Stiefkinder als Verwandte des aufenthaltsberechtigten Angehörigen einer Vertragspartei gelten oder nicht, bisher noch nicht abschliessend beantwortet (vgl. BGE 130 II 1 E. 3.5 S. 7 ff. mit zahlreichen Hinweisen auf die Literatur; vgl. sodann die Urteile 2A.425/2003 E. 3.2 vom 5. März 2004 in ZBl 106/2005 S. 532, 2A.94/2004 vom 6. August 2004 E. 4.2 in Pra 2005 Nr. 15 S. 102; ASTRID EPINEY/TAMARA CIVITELLA, Zur schweizerischen Rechtsprechung zum Personenfreizügigkeitsabkommen, in: Achermann et al. [Hrsg.], Jahrbuch für Migrationsrecht 2007/2008, 2008, 237). Bei der Auslegung des analoge Rechtsverhältnisse regelnden Art. 3 Abs. 6 Anhang I FZA schloss sich das Bundesgericht in einem Urteil vom 25. Mai 2005 der weiten Auslegung des EuGH an (Urteil 2A.475/2004), relativierte dies aber wieder in einem weiteren Urteil vom 14. März 2008 (Urteil 2C_33/2007 in RtiD 2008 II S. 320).
4. 4.1 Das Urteil Baumbast (C-413/1999; vgl. vorne E. 3.4) erging nach der Unterzeichnung des Freizügigkeitsabkommens. Der Sachverhalt, der vom EuGH zu beurteilen war, hatte sich allerdings bereits vor Vertragsschluss ereignet. Nach Art. 16 Abs. 2 FZA ist die einschlägige Rechtsprechung vor dem Zeitpunkt der Unterzeichnung zu berücksichtigen, was dafür spricht, dass grundsätzlich nur die bereits gefällten und damit den Vertragsparteien bekannten Urteile gemeint sind. Das Urteil Baumbast (C-413/1999; vgl. vorne E. 3.4) ist daher grundsätzlich nicht verbindlich (vgl. E. 3.1 hiervor).
4.2 Für die Schweiz nur bedingt massgebend sind sodann die Regeln über die Unionsbürgerschaft. Daran können nur Rechtsfolgen anknüpfen, die dem Sinn und Geist des Freizügigkeitsabkommens entsprechen und diesem zugrundeliegen. Bei den Bestimmungen über den Familiennachzug ist ein solcher Zusammenhang - etwa im Unterschied zum Petitionsrecht oder zum Recht auf diplomatische Vertretung (vgl. das Urteil des Bundesgerichts 2C_196/2009 vom 29. September 2009 E. 3.6.3) - freilich vielfach gegeben, auch wenn für jede Einzelfrage geprüft werden muss, wie es sich damit verhält. So sind insbesondere mit der RL 2004/38/EG neu eingeführte Rechte (dazu Astrid Epiney/Andrea Faeh, Zum Aufenthaltsrecht von Familienangehörigen im europäischen Gemeinschaftsrecht, in: Achermann et al. [Hrsg.], Jahrbuch für Migrationsrecht 2005/2006, 2006, 59 f.) wie das bedingungslose Recht auf Daueraufenthalt nach ununterbrochenem fünfjährigem rechtmässigem Aufenthalt (nach Art. 16 RL 2004/38/EG) oder das voraussetzungslose Aufenthaltsrecht von bis zu drei Monaten (gemäss Art. 6 RL 2004/38/EG) für die Schweiz nicht verbindlich.
4.3 Für die Berücksichtigung des Urteils Baumbast (C-413/1999; vgl. vorne E. 3.4) spricht in diesem Sinne, dass der Entscheid des EuGH nicht an neues Sekundärrecht, sondern an eine Rechtsprechung anknüpft, die bereits vor Abschluss des Freizügigkeitsabkommens ergangen und damit für die Anwendung desselben massgebend ist. Auch wenn dabei nicht genau dieselbe Rechtsfrage zu entscheiden war, so war nach der bei Vertragsabschluss bereits bekannten Praxis von einer eher weiten Auslegung der Bestimmungen über die Familienvereinigung auszugehen. Insbesondere berief sich der EuGH nicht erst im Urteil Baumbast (C-413/1999; vgl. vorne E. 3.4), sondern schon im Urteil Echternach (C-389/87; vgl. vorne E. 3.4) auf die Grundnorm des damaligen Art. 18 des EG-Vertrages (heute Art. 21 der konsolidierten Fassung des Vertrags über die Arbeitsweise der Europäischen Union vom 13. Dezember 2007 [Vertrag von Lissabon]; ABl. Nr. C 115 vom 9. Mai 2008, S. 47 ff.). Diese bildete letztlich die Grundlage der Regelung über den Familiennachzug und galt beim Abschluss des Freizügigkeitsabkommens in der Fassung des Vertrags von Amsterdam von 1997, wobei der hier massgebliche Regelungsgehalt durch die Änderung gemäss dem Vertrag von Nizza von 2003 keine wesentlichen Neuerungen erfuhr. Das Urteil Baumbast stützte sich sodann ausdrücklich auf die Verordnung Nr. 1612/68, der auch das Freizügigkeitsabkommen nachgebildet ist, und gibt damit die einschlägige Auslegung der entsprechenden gemeinschaftsrechtlichen Bestimmungen über die Familienvereinigung wieder. Art. 10 Abs. 1 lit. a der Verordnung Nr. 1612/68 hat im Übrigen in den deutsch-, französisch- und italienischsprachigen Fassungen jeweils denselben Wortlaut wie das Freizügigkeitsabkommen. Die entsprechende Auslegung der Verordnung Nr. 1612/68 durch den Gerichtshof wurde nachträglich durch Erlass der Richtlinie 2004/38/EG ausdrücklich und deutlich ins geschriebene ordentliche Recht überführt (vgl. Art. 2 Ziff. 2 lit. c RL 2004/38/EG). Damit kann heute kein Zweifel mehr bestehen, welche gemeinschaftsrechtliche Regelung gilt. Im hier fraglichen Zusammenhang führte die Neufassung der einschlägigen Bestimmungen allerdings zu keinen wesentlichen Änderungen, sondern sie diente lediglich der Klarstellung.
4.4 Die Anwendung der Bestimmungen über den Familiennachzug auf Stiefkinder entspricht der Zweckrichtung der Regelung der Familienvereinigung. Es leuchtet nicht ein, weshalb ein Anspruch auf Nachzug der Verwandten des Ehegatten in aufsteigender Linie bestehen soll, nicht aber für dessen Nachkommen. Auch wenn die Beziehung Erwachsener zu den Eltern oder zu weiteren Vorfahren durchaus bedeutsam sein kann, so ist diejenige zu den Kindern bzw. sonstigen Nachkommen meist enger, jedenfalls solange diese minderjährig sind bzw. ihnen Unterhalt gewährt wird. Eine rechtliche Ordnung, die das Zusammenleben mit der Nachkommenschaft ermöglicht oder fördert, erscheint daher gebotener als eine solche, die dasselbe mit den Vorfahren vorsieht. Auch aus diesem Grunde rechtfertigt sich eine einschränkende Auslegung von Art. 3 Anhang I FZA nicht. Da die Bestimmung in lit. b ausdrücklich einen Anspruch auf Anwesenheitsbewilligung für die Verwandten des Ehegatten in aufsteigender Linie vorsieht, ist lit. a in dem Sinne zu verstehen, dass es um so mehr auch einen solchen für dessen Verwandte in absteigender Linie gibt.
4.5 Schliesslich wird im Schrifttum weitgehend einhellig ebenfalls die Meinung vertreten, es sei in Anlehnung an die Rechtsprechung des EuGH davon auszugehen, dass Art. 3 Abs. 2 lit. a FZA auch die Stiefkinder erfasse. Die entsprechenden Begründungen folgen dabei im Wesentlichen dem hier wiedergegebenen Argumentationsmuster (dazu Alvaro Borghi, La libre circulation des personnes entre la Suisse et l'UE, 2010, Rz. 420 ff.; Astrid Epiney, Die schweizerische Rechtsprechung zum Personenfreizügigkeitsabkommen - ein Überblick, in: Achermann et al. [Hrsg.], Jahrbuch für Migrationsrecht 2004/2005, 2005, 148; Laurent Merz, Le droit de séjour selon l'ALCP et la jurisprudence du Tribunal fédéral, RDAF 65/2009 I, 281; Marc Spescha/ Hanspeter Thür/Andreas Zünd/Peter Bolzli, Migrationsrecht, 2. Aufl., 2009, Nr. 22, N. 9 zu Art. 3 Anhang I FZA; vgl. auch Alberto Achermann/Martina Caroni, § 6 Einfluss der völkerrechtlichen Praxis auf das schweizerische Migrationsrecht, in: Uebersax/Rudin/Hugi Yar/ Geiser [Hrsg.], Ausländerrecht, 2. Aufl., 2009, Rz. 6.51).
4.6 Insgesamt sprechen mithin analoge Überlegungen wie bei der Anpassung der bundesgerichtlichen Rechtsprechung an diejenige des EuGH i.S. Metock (C-127/08; vgl. vorne E. 2.4) auch hier für eine Angleichung der Praxis zum Freizügigkeitsrecht an diejenige zum Gemeinschaftsrecht. Es sind keine triftigen Gründe erkennbar, weshalb es innerhalb der Europäischen Gemeinschaft und in deren Verhältnis mit der Schweiz zwei unterschiedliche Freizügigkeitsregelungen geben sollte. Das Interesse an einer parallelen Rechtslage und mithin an einem möglichst einheitlichen Freizügigkeitsraum geht vielmehr vor. Angesichts der systematischen Zusammenhänge drängt sich eine solche Schlussfolgerung daher auf.
5. 5.1 Die Beschwerdeführer 2 und 3 sind noch nicht 21 Jahre alt. Sie fallen demnach unter den Anwendungsbereich von Art. 3 Abs. 2 Anhang I FZA.
5.2 Auch nach dem Freizügigkeitsrecht ist der Familiennachzug freilich nicht vorbehaltlos zulässig. Vielmehr ist erforderlich, dass der EU-Angehörige, um dessen Personenfreizügigkeit es letztlich geht, mit dem Nachzug der Stiefkinder einverstanden ist, da dieser sonst gar nicht der Gewährleistung des Freizügigkeitsrechts dient. Weiter sind analog zum Gemeinschaftsrecht und gemäss denselben Grundsätzen (vgl. insbes. Art. 35 RL 2004/38/EG) familienrechtliche Scheinbeziehungen vom Nachzugsrecht auszuschliessen. In diesem Sinne ist zu verlangen, dass bereits vor der Familienvereinigung ein (soziales) Familienleben tatsächlich bestanden hat, wobei die Angehörigen freilich nicht zusammengewohnt, wohl aber ihre Beziehung mit minimaler Intensität gelebt haben müssen. Bei Minderjährigen hat der nachziehende Ehegatte sodann die zivilrechtliche Verantwortung für das Kind zu tragen, d.h. er muss entweder über das Sorgerecht oder bei geteiltem Sorgerecht über das Einverständnis des anderen Elternteils verfügen. Damit die nachzuziehenden Angehörigen bei der freizügigkeitsberechtigten Person Wohnung nehmen können (vgl. Art. 3 Abs. 1 erster Satz Anhang I FZA), hat dafür auch eine Wohnung vorhanden zu sein, die den für Inländer geltenden normalen Anforderungen entspricht (vgl. Art. 3 Abs. 1 zweiter Satz Anhang I FZA). Zu beachten ist überdies der Vorbehalt der öffentlichen Ordnung, Sicherheit und Gesundheit gemäss Art. 5 Anhang I FZA. Schliesslich darf der Nachzugsentscheid der Eltern mit Blick auf die Anforderungen des Übereinkommens vom 20. November 1989 über die Rechte des Kindes (Kinderrechtskonvention, KRK; SR 0.107) nicht in offensichtlichem Widerspruch zum Kindeswohl stehen.
5.3 Im vorliegenden Fall ist unbestritten, dass die Beschwerdeführer ihre familiäre Beziehung in einem Mass gelebt haben, wie dies angesichts der räumlichen Distanz möglich war bzw. vernünftigerweise erwartet werden darf. In den Verfahrensakten befindet sich sodann eine schriftliche und notariell beglaubigte Bestätigung vom 23. Oktober 2007 der Ehefrau des Beschwerdeführers, womit diese ihr Einverständnis mit dem Nachzug der beiden Kinder ihres Ehemannes erklärt. Die Akten enthalten ebenfalls ein schriftliches Exemplar mit Übersetzung eines Beschlusses des Kommunalgerichts in Suharekë vom 3. Januar 2008, mit dem die Beschwerdeführer 2 und 3 dem Beschwerdeführer 1 zivilrechtlich zur Sorge, Erziehung und Bildung anvertraut werden. Aktenkundig ist überdies die schriftliche Zustimmungserklärung der Mutter zur Zusammenführung der beiden Kinder mit dem Vater in der Schweiz. Auch liegt ein Mietvertrag vor, wonach der Beschwerdeführer 1 und seine Ehefrau ab dem 1. August 2007 eine Dreieinhalbzimmerwohnung gemietet haben, die mit zwei bis vier Personen belegt werden darf und sich damit als den Bedürfnissen der Familie angemessen erweist. Anhaltspunkte für die Anwendbarkeit des die Freizügigkeitsrechte beschränkenden Vorbehalts der öffentlichen Ordnung, Sicherheit und Gesundheit gemäss Art. 5 Anhang I FZA gibt es nicht. Von keiner Seite wurden denn auch solche Einwände im Verlauf des ganzen Verfahrens vor allen Instanzen glaubwürdig vorgetragen. Schliesslich sind keine Gründe ersichtlich, die auf einen offensichtlichen Widerspruch zum Kindeswohl hinweisen.
5.4 Dem Gesuch um Nachzug der Beschwerdeführer 2 und 3 ist somit gestützt auf das Freizügigkeitsrecht stattzugeben. Der angefochtene Entscheid verstösst gegen das Freizügigkeitsabkommen, insbesondere gegen Art. 7 lit. d FZA und Art. 3 Anhang I FZA, weshalb es sich erübrigt, zu prüfen, ob er allenfalls vor Art. 8 EMRK bzw. Art. 13 BV standhält.
6. 6.1 Die Beschwerde erweist sich als begründet und ist gutzuheissen. Der angefochtene Entscheid muss aufgehoben werden, und das kantonale Migrationsamt ist anzuweisen, den Beschwerdeführern 2 und 3 je eine Aufenthaltsbewilligung EG/EFTA zu erteilen. Der Eventualantrag auf Rückweisung der Sache an die Vorinstanz wird damit gegenstandslos. Das Verwaltungsgericht wird freilich über die Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens neu zu entscheiden haben.
6.2 Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 66 Abs. 4 BGG). Hingegen hat der Kanton Zürich die Beschwerdeführer als Solidargläubiger für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Zürich, 4. Kammer, vom 4. März 2009 wird aufgehoben.
2. Die Sicherheitsdirektion des Kantons Zürich, Migrationsamt, wird angewiesen, den Beschwerdeführern 2 und 3 je eine Aufenthaltsbewilligung EG/EFTA zu erteilen.
3. Das Verwaltungsgericht des Kantons Zürich hat über die Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens neu zu entscheiden.
4. Es werden keine Kosten erhoben.
5. Der Kanton Zürich hat die Beschwerdeführer als Solidargläubiger für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
6. Dieses Urteil wird den Beschwerdeführern, der Sicherheitsdirektion (Migrationsamt) und dem Regierungsrat sowie dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und 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 Uebersax