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. 