Sachverhalt:
A. Die Zürichsee Schifffahrtsgesellschaft bot während vieler Jahre im Sommerhalbjahr einen Frühkurs an, mit dem Pendler aus den Gemeinden Kilchberg, Thalwil, Erlenbach und Küsnacht nach Zürich fuhren (sog. Gipfelischiff). Der Zürcher Verkehrsverbund beschloss, diese Schiffsverbindung für die Fahrplanperiode 2009/10 zu streichen, weil es seit der Einführung einer kleinen Abendrundfahrt nicht mehr möglich sei, das "Gipfelischiff" zu den Grenzkosten weiter zu betreiben. Der Regierungsrat des Kantons Zürich wies einen Rekurs, den die Gemeinden Erlenbach, Küsnacht und Thalwil gegen die Abschaffung des "Gipfelischiffs" erhoben hatten, am 25. Februar 2009 ab, soweit er nicht gegenstandslos geworden war. Das Verwaltungsgericht des Kantons Zürich trat am 30. April 2009 auf eine Beschwerde der erwähnten Gemeinden gegen den Entscheid des Regierungsrats nicht ein.
B. Die Gemeinden Erlenbach, Küsnacht und Thalwil haben gegen den Regierungsratsbeschluss Beschwerde ebenfalls beim Bundesgericht eingereicht. Sie beantragen, diesen Beschluss aufzuheben und den Verbundfahrplan 2009/10 insoweit aufzuheben, als darin der Frühkurs 6 der Zürichsee Schifffahrtsgesellschaft (sog. Gipfelischiff) abgeschafft und die Kurse 55 und 56 (sog. kleine Abendrundfahrt) beibehalten werde. Eventualiter sei lediglich die Abschaffung des erwähnten Frühkurses aufzuheben.
Der Zürcher Verkehrsverbund ersucht um Abweisung der Beschwerde, soweit darauf einzutreten sei.
Der Regierungsrat des Kantons Zürich beantragt, es sei auf die Beschwerde nicht einzutreten, eventuell sei sie abzuweisen.
C. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat am 2. Juni 2009 ein Gesuch der Beschwerdeführerinnen um vorsorgliche Massnahmen (Betreiben des "Gipfelischiffs" während des bundesgerichtlichen Verfahrens) abgewiesen.

Erwägungen:
1. 1.1 Die Beschwerdeführerinnen werfen dem Regierungsrat eine Verletzung ihrer Gemeindeautonomie vor. Da sie der Entscheid über den Verbundfahrplan in ihren hoheitlichen Belangen berührt, sind sie gemäss <ref-law> zur Erhebung dieser Rüge legitimiert. Ob ihnen die beanspruchte Autonomie im fraglichen Bereich tatsächlich zukommt, ist - sofern es nicht von vornherein offensichtlich an an einem kommunalen Autonomiebereich fehlt - nicht eine Frage des Eintretens, sondern der materiellen Beurteilung (<ref-ruling> E. 1.2).
1.2 Es kann offen bleiben, ob auch die übrigen Voraussetzungen zur Geltendmachung einer Autonomieverletzung erfüllt sind, namentlich ob der Entscheid über den Verbundfahrplan überhaupt als anfechtbarer Entscheid anzusehen ist. Denn den Zürcher Gemeinden kommt bei der Festlegung des Verbundangebots keine Autonomie zu. Die Anerkennung eines kommunalen Autonomiebereichs setzt voraus, dass das übergeordnete Recht den Gemeinden im fraglichen Sachbereich erhebliche Entscheidungsfreiheit einräumt (<ref-ruling> E. 2a S. 226 f.). Daran fehlt es hier. Das Angebot des Zürcher Verkehrsverbunds wird gemäss § 19 Abs. 1 des kantonalen Gesetzes über den öffentlichen Personenverkehr vom 6. März 1988 (PVG/ZH) vom Verkehrsrat festgesetzt. Im dabei durchzuführenden Fahrplanverfahren haben die Gemeinden zwar Mitwirkungsrechte (vgl. <ref-law>/ZH); doch liegt es in der Natur der Sache, dass das Angebot für das ganze Verbundgebiet von einem überkommunalen Organ bestimmt werden muss und den Gemeinden dabei überhaupt keine Entscheidbefugnisse zustehen.
1.3 Die Beschwerde ist demnach abzuweisen, soweit damit eine Verletzung der Gemeindeautonomie geltend gemacht wird.
2. 2.1 Nach Auffassung der Beschwerdeführerinnen beruht die Abschaffung des "Gipfelischiffs" auf einer willkürlichen und rechtsungleichen Anwendung von § 18 Abs. 1 Satz 2, § 20 und 29 PVG/ZH sowie auf einer offensichtlich unrichtigen Sachverhaltsfeststellung und einer Verletzung ihres Anspruchs auf rechtliches Gehör (<ref-law>). Die Legitimation zur Erhebung dieser Rügen leiten sie aus der allgemeinen Regelung der Beschwerdebefugnis in <ref-law> ab.
2.2 Die angerufene Norm ist grundsätzlich auf Privatpersonen zugeschnitten. Nach der Rechtsprechung des Bundesgerichts kann jedoch auch das Gemeinwesen das allgemeine Beschwerderecht in Anspruch nehmen, wenn es durch die angefochtene Verfügung gleich oder ähnlich wie ein Privater betroffen ist. Ausserdem anerkennt die neuere Praxis die Beschwerdebefugnis des Gemeinwesens ebenfalls dann, wenn dieses durch den fraglichen Akt in qualifizierter Weise in schutzwürdigen hoheitlichen Interessen berührt wird. Allerdings sind Gemeinwesen gestützt auf <ref-law> nur restriktiv zur Beschwerdeführung zuzulassen (<ref-ruling> E. 1.3 S. 47).
2.3 Die Beschwerdeführerinnen verweisen zur Begründung ihrer Legitimation auf die Praxis des Bundesrats, der auf die Rechtsmittel von Gemeinden eingetreten ist, die sich gegen die Umwandlung von bedienten Stationen in unbediente Haltestellen wehrten (vgl. VPB 43/1979 Nr. 47 E. 1 S. 225 f. betr. die Station Lamone-Cadempino der SBB und VPB 44/1980 Nr. 60 E. 1 S. 247 betr. die Station Seewis-Valzeina der RhB). Es kann offen bleiben, ob diese Rechtsprechung, die vor dem Hintergrund der damaligen Eisenbahngesetzgebung für das verwaltungsinterne Beschwerdeverfahren entwickelt wurde, auch für das bundesgerichtliche Verfahren Geltung beanspruchen kann. Jedenfalls hat der Entscheid über die Streichung der fraglichen Schiffsverbindung keine vergleichbare Tragweite wie die Umwandlung einer bedienten Bahnstation in eine unbediente Haltestelle. So zählt der Frühkurs, der aufgehoben werden soll, nicht zur Grundversorgung, sondern zum sog. übrigen Verbundangebot im Sinne von <ref-law>/ZH. Für die verkehrsmässige Erschliessung der beschwerdeführenden Gemeinden kommt dem Frühkurs keine erhebliche Bedeutung zu. Das belegen auch die unbestritten geringe Auslastung und der Umstand, dass der Kurs schon bisher nur im Sommerhalbjahr angeboten wurde. Es kann deshalb nicht gesagt werden, dass die Streichung des sog. Gipfelischiffs im Verbundfahrplan 2009/10 die Beschwerdeführerinnen in qualifizierter Weise in schutzwürdigen hoheitlichen Interessen berühre. Ihre Legitimation, neben der Gemeindeautonomie weitere Rügen zu erheben, ist daher zu verneinen. Auf ihr Rechtsmittel ist in diesem Umfang nicht einzutreten.
3. Aus diesen Erwägungen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind keine Kosten zu erheben (<ref-law>). Der Beschwerdegegner hat als mit öffentlich-rechtlichen Aufgaben betraute Organisation keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Es werden keine Kosten erhoben.
3. Dem Beschwerdegegner wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Verfahrensbeteiligten sowie dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 21. Oktober 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Küng