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. 