Faits: A. Lors de la votation cantonale organisée le 27 septembre 2009 à Genève, les citoyens étaient invités à se prononcer notamment sur l'objet cantonal intitulé "Acceptez-vous la loi sur l'imposition des personnes physiques (LIPP), du 12 juin 2009 (D 3 08 - 10199)?". Selon la brochure explicative remise aux électeurs, l'acceptation de cet objet induirait des baisses de l'impôt cantonal estimées à 321 millions de francs en 2010 et 387 millions en 2011, ce qui entraînerait également une baisse des rentrées fiscales des communes du canton. Le 31 juillet 2009, un groupement dénommé "Ville de Genève" avait déposé auprès du service compétent une prise de position au sens de l'art. 23 al. 1 de la loi genevoise sur l'exercice des droits politiques (LEDP; RSG A 5 05). Munie de cinquante-sept signatures de citoyens genevois, cette prise de position appelait à rejeter l'objet susmentionné. Parmi les signataires figuraient quatre des cinq membres du Conseil administratif de la Ville de Genève, à savoir Sandrine Salerno, Manuel Tornare, Patrice Mugny et Rémy Pagani, maire de la ville. Par ailleurs, selon un article paru dans "la Tribune de Genève" en août 2009, le maire de la ville avait annoncé que le budget du numéro de septembre du " tous-ménages" intitulé "Vivre à Genève" serait consacré à inciter les habitants de la ville à rejeter l'objet précité. Dans un autre article, la conseillère administrative Sandrine Salerno précisait que la publication en question serait réduite de quarante-cinq à huit pages et que l'argent ainsi économisé serait consacré notamment à la confection de banderoles, d'affiches et d'autocollants, ainsi qu'à la publication d'annonces dans les journaux. Elle estimait le coût de cette campagne à moins de 70'000 francs. B. Le 26 août 2009, le citoyen genevois Renaud Gautier a saisi le Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) d'un recours en matière de droits politiques dirigé contre la publication de la prise de position intitulée "Ville de Genève" ainsi que contre la campagne annoncée par la Ville de Genève. Par décision du 8 septembre 2009, la présidente du Tribunal administratif a admis une requête de mesures provisionnelles, faisant interdiction au groupement de se prévaloir de l'appellation "Ville de Genève" et à la Ville de Genève d'intervenir dans la campagne. Par arrêt du 15 septembre 2009, le Tribunal administratif a admis le recours de Renaud Gautier dans la mesure où il était recevable. En substance, il a constaté que la prise de position du groupement "Ville de Genève" violait les droits politiques. Il a fait interdiction à la Ville de Genève d'intervenir dans la campagne en cours et aux signataires de la prise de position "Ville de Genève" de s'en prévaloir dans la campagne, sous la menace de la peine prévue à l'art. 292 CP. C. Par acte du 21 septembre 2009, la Ville de Genève et le groupement "Ville de Genève" interjettent un recours en matière de droit public. Ils concluent à l'annulation de la décision du Tribunal administratif du 15 septembre 2009 et demandent au Tribunal fédéral de constater que la Ville de Genève a le droit d'intervenir dans la campagne et que le groupement "Ville de Genève" a le droit de se prévaloir de cette appellation. Subsidiairement, pour le cas où la décision du Tribunal fédéral interviendrait après la votation en cause, ils demandent que l'arrêt attaqué soit annulé et que le Tribunal fédéral constate que les deux recourants avaient le droit d'intervenir dans la campagne et que l'interdiction contestée violait le droit. Les recourants requièrent par ailleurs, sur mesures provisionnelles urgentes, que la Ville de Genève, Sandrine Salerno et Rémy Pagani soient autorisés à organiser un débat contradictoire ou à y participer dans le cadre de la campagne en cause. Le Tribunal administratif a renoncé à se déterminer. Le Conseil d'Etat et Renaud Gautier ont présenté des observations, concluant au rejet du recours dans la mesure de sa recevabilité. Les recourants et Renaud Gautier ont formulé des observations complémentaires. D. Par ordonnance du 23 septembre 2009, le Président de la Ire Cour de droit public a rejeté la requête de mesures provisionnelles urgentes dans la mesure où elle n'était pas sans objet.