Sachverhalt:
A. Am 15. Juni 2009 hiess der Grosse Gemeinderat der Stadt Winterthur einen Kredit von Fr. 722'000.-- für bauliche Anpassungen im Anbau eines Gebäudes an der Y._strasse zur Nutzung als "Anlaufstelle für Randständige" gut.
Mit Beschluss vom 12. August 2009 stellte der Stadtrat Winterthur fest, dass das Referendum gegen den Kredit zustande gekommen sei, und setzte den Abstimmungstermin auf den 29. November 2009 fest.
Am 6. November 2009 erhob das Referendumskomitee Stimmrechtsrekurs an den Bezirksrat Winterthur unter anderem mit den Anträgen, es sei festzustellen, dass die Abstimmungsunterlagen irreführend seien, und der Stadtrat sei anzuweisen, die Fehlinformationen zu korrigieren und den Stimmberechtigten die korrigierten Abstimmungsunterlagen bis spätestens 16. November 2009 zuzustellen; eventualiter sei die Abstimmung zu verschieben oder zu wiederholen.
Die Abstimmung fand am 29. November 2009 statt, und die Vorlage wurde mit 62,1 %, respektive 19'986 Ja-Stimmen gegen 12'210 Nein-Stimmen, angenommen.
Mit Beschluss vom 26. März 2010 wies der Bezirksrat Winterthur den Stimmrechtsrekurs des Referendumskomitees ab, soweit er auf diesen eintrat.
B. Am 24. April 2010 erhob das Referendumskomitee Stimmrechtsbeschwerde an das Verwaltungsgericht des Kantons Zürich. Dieses wies die Beschwerde mit Entscheid vom 6. August 2010 ab.
C. Mit Beschwerde vom 9. September 2010 an das Bundesgericht ficht das Referendumskomitee den Entscheid des Verwaltungsgerichts an und beantragt, der vom Verwaltungsgericht anerkannte Mangel in der Gestaltung der Abstimmungszeitung sei als erheblich zu erkennen; ebenso sei die Nichterwähnung der Folgen der bestehenden Rechtstitel (Dienstbarkeit) in der Abstimmungszeitung als Unterdrückung von wichtigen Informationen zu erkennen. Die Volksabstimmung vom 29. November 2009 sei daher zu kassieren, und es sei eine Wiederholung der Abstimmung anzuordnen.
D. Der Stadtrat Winterthur beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Der Bezirksrat Winterthur und das Verwaltungsgericht verzichten auf eine Vernehmlassung zur Beschwerde. Das Referendumskomitee verzichtet auf eine abschliessende Stellungnahme.

Erwägungen:
1. 1.1 Mit der Beschwerde nach <ref-law> kann die Verletzung von politischen Rechten beim Bundesgericht geltend gemacht werden. Dazu zählt die Rüge, Abstimmungserläuterungen seien mangelhaft und verhinderten eine zuverlässige und unverfälschte Willensbildung und -äusserung der Stimmberechtigten im Sinne von <ref-law>. Von der Beschwerde werden sowohl eidgenössische als auch kantonale und kommunale Stimmrechtssachen erfasst (<ref-law>).
Das Beschwerderecht steht gemäss <ref-law> jeder Person zu, die in der betreffenden Angelegenheit stimmberechtigt ist. Ein besonderes (rechtliches) Interesse in der Sache selbst ist nicht erforderlich (vgl. <ref-ruling> E. 1.3.3 S. 176). Ebenfalls als legitimiert gelten nach der Rechtsprechung die politischen Parteien, die im Gebiet des betreffenden Gemeinwesens tätig sind, sowie politische Vereinigungen, namentlich ad hoc gebildete, mit juristischer Persönlichkeit ausgestattete Initiativ- und Referendumskomitees (<ref-ruling> E. 1.3.1 S. 175; Urteil 1C_247/2008 vom 21. Januar 2009 E. 1.1, in: Pra 2009 Nr. 83 S. 564; je mit Hinweisen). Soweit es sich beim Referendumskomitee nicht um eine juristische Person mit eigener Rechtspersönlichkeit handelt, sind die Mitglieder des Komitees als in Winterthur Stimmberechtigte je einzeln zur Beschwerde legitimiert. Im Sinn einer Vereinfachung sind sie unter dem Namen des Referendumskomitees gemeinsam zur Beschwerdeführung zuzulassen (vgl. BGE 1C_174/2010 vom 14. Dezember 2010 E. 1.2).
1.2 Das beschwerdeführende Referendumskomitee (nachfolgend als "die Beschwerdeführer" bezeichnet) beantragt im Hauptpunkt die Aufhebung der Volksabstimmung vom 29. November 2009 und deren Wiederholung. Diese Anträge sind zulässig. Betreffend die Rechtsbegehren, der Mangel in der Gestaltung der Abstimmungszeitung und die Nichterwähnung der bestehenden Dienstbarkeit in den Abstimmungserläuterungen seien als erheblich zu erkennen, fehlt es hingegen an einem besonderen Feststellungsinteresse, weshalb hierauf nicht eingetreten werden kann (vgl. insoweit Urteil 1C_385/2009 vom 29. September 2009 E. 1.2). Diese Einwände könnten jedoch, sollten sie berechtigt sein und sich auf das Abstimmungsergebnis ausgewirkt haben, zur Aufhebung und Wiederholung der Volksabstimmung führen. Unter diesem Blickwinkel ist nachfolgend darauf einzugehen.
2. 2.1 Die Beschwerdeführer wenden sich gegen den Inhalt und die Gestaltung der Abstimmungszeitung. Einerseits bringen sie vor, die auf dem Grundstück an der Y._strasse lastende Dienstbarkeit hätte in den Abstimmungsunterlagen erwähnt werden müssen, da eine allenfalls notwendige Ablösung der Dienstbarkeit erhebliche Kostenfolgen zeitigen würde. Andererseits rügen die Beschwerdeführer, ihren Argumenten sei deutlich weniger Platz eingeräumt worden, da ihre Stellungnahme in einer sehr kleinen Schriftgrösse abgedruckt worden sei. Diese beiden Mängel seien erheblich und rechtfertigten eine Aufhebung und Wiederholung der Abstimmung.
2.2 Die Vorinstanz erwägt, eine Erwähnung der fraglichen Dienstbarkeit in den Abstimmungserläuterungen sei nicht zwingend nötig gewesen. Soweit die Beschwerdeführer hingegen die Gestaltung der Abstimmungszeitung rügten, sei ihr Vorbringen stichhaltig. Während der Stadtrat seine Argumentation optisch ansprechend und in normaler Schriftgrösse ausgebreitet habe, seien die Argumente des Referendumskomitees auf einer halben Seite in gedrängter Form dargestellt worden. Für die Stellungnahme des Referendumskomitees eine deutlich kleinere Schriftgrösse zu verwenden, gehe nicht an. Da die Beschwerdeführer ihre Position jedoch hätten aufzeigen können, handle es sich nur um einen leichten Mangel, der für den Ausgang der Abstimmung bloss von geringer Bedeutung gewesen sein dürfte. Dies gelte umso mehr, als die Beschwerdeführer ihren Standpunkt auch in den Medien hätten darlegen können. Schliesslich spreche auch das deutliche Abstimmungsresultat gegen die Annahme, dass sich der Mangel auf das Ergebnis entscheidend ausgewirkt habe.
2.2 Die Vorinstanz erwägt, eine Erwähnung der fraglichen Dienstbarkeit in den Abstimmungserläuterungen sei nicht zwingend nötig gewesen. Soweit die Beschwerdeführer hingegen die Gestaltung der Abstimmungszeitung rügten, sei ihr Vorbringen stichhaltig. Während der Stadtrat seine Argumentation optisch ansprechend und in normaler Schriftgrösse ausgebreitet habe, seien die Argumente des Referendumskomitees auf einer halben Seite in gedrängter Form dargestellt worden. Für die Stellungnahme des Referendumskomitees eine deutlich kleinere Schriftgrösse zu verwenden, gehe nicht an. Da die Beschwerdeführer ihre Position jedoch hätten aufzeigen können, handle es sich nur um einen leichten Mangel, der für den Ausgang der Abstimmung bloss von geringer Bedeutung gewesen sein dürfte. Dies gelte umso mehr, als die Beschwerdeführer ihren Standpunkt auch in den Medien hätten darlegen können. Schliesslich spreche auch das deutliche Abstimmungsresultat gegen die Annahme, dass sich der Mangel auf das Ergebnis entscheidend ausgewirkt habe.
2.3 2.3.1 Die in <ref-law> als Grundrecht verankerte Abstimmungsfreiheit gibt den Stimmberechtigten Anspruch darauf, dass kein Abstimmungsergebnis anerkannt wird, das nicht ihren freien Willen zuverlässig und unverfälscht zum Ausdruck bringt. Es soll garantiert werden, dass jede stimmberechtigte Person ihren Entscheid gestützt auf einen möglichst freien und umfassenden Prozess der Meinungsbildung treffen und entsprechend mit ihrer Stimme zum Ausdruck bringen kann. Die Abstimmungsfreiheit gewährleistet die für den demokratischen Prozess und die Legitimität direktdemokratischer Entscheidungen erforderliche Offenheit der Auseinandersetzung (<ref-ruling> E. 2 S. 293 f.; <ref-ruling> E. 3.1 S. 108; <ref-ruling> E. 3.1 S. 447; je mit Hinweisen).
2.3.2 Das Ergebnis eines Urnengangs kann unter anderem durch eine unzulässige behördliche Beeinflussung der Willensbildung der Stimmberechtigten im Vorfeld der Abstimmung verfälscht werden. Eine solche Beeinflussung fällt namentlich in Bezug auf amtliche Abstimmungserläuterungen in Betracht (vgl. <ref-ruling> E. 2 S. 294 und E. 4.2 S. 297 ff.; <ref-ruling> E. 3a S. 272; Urteile des Bundesgerichts 1C_412/2007 vom 18. Juli 2008 E. 4 und 1C_392/2009 vom 1. Dezember 2009 E. 2; je mit Hinweisen). Nach der Rechtsprechung sind behördliche Abstimmungsbotschaften, in denen eine Vorlage erklärt und zur Annahme oder Ablehnung empfohlen wird, unter dem Gesichtswinkel der Abstimmungsfreiheit zulässig. Die Behörde ist dabei zwar nicht zur Neutralität verpflichtet - und darf eine Abstimmungsempfehlung abgeben -, wohl aber zur Objektivität. Sie verletzt ihre Pflicht zu objektiver Information, wenn sie über den Zweck und die Tragweite der Vorlage falsch orientiert. Dem Erfordernis der Objektivität genügen Abstimmungserläuterungen, wenn die Aussagen wohlabgewogen sind und beachtliche Gründe dafür sprechen, wenn sie ein umfassendes Bild der Vorlage mit ihren Vor- und Nachteilen abgeben und den Stimmberechtigten eine Beurteilung ermöglichen oder wenn sie trotz einer gewissen Überspitzung nicht unwahr und unsachlich bzw. lediglich ungenau und unvollständig sind. Die Behörde muss sich nicht mit jeder Einzelheit einer Vorlage befassen und nicht alle denkbaren Einwendungen, welche erhoben werden könnten, erwähnen. Dies ist schon deshalb entbehrlich, weil der behördliche Bericht keineswegs das einzige Informationsmittel im demokratischen Meinungsbildungsprozess darstellt und die Stimmberechtigten von den für oder gegen die Vorlage sprechenden Argumenten auch noch über andere Quellen wie namentlich via Medien Kenntnis erhalten können. Das Gebot der Sachlichkeit verbietet indessen, in den Abstimmungserläuterungen für den Entscheid der Stimmbürger wichtige Elemente zu unterdrücken oder Argumente von gegnerischen Referendumskomitees falsch wiederzugeben (vgl. <ref-ruling> E. 3.2 S. 294; <ref-ruling> E. 3b S. 273; Urteil 1C_392/2009 vom 1. Dezember 2009 E. 2; vgl. zum Ganzen Michel Besson, Behördliche Information vor Volksabstimmungen, 2003, S. 182 ff., 208 ff. und 250 ff.).
2.3.3 Stellt das Bundesgericht im Vorfeld einer Abstimmung oder bei deren Durchführung Mängel fest, so hebt es den Urnengang nur auf, wenn die gerügten Unregelmässigkeiten erheblich sind und das Ergebnis beeinflusst haben könnten. Die Beschwerdeführenden müssen in einem solchen Fall allerdings nicht nachweisen, dass sich der Mangel auf das Ergebnis der Abstimmung entscheidend ausgewirkt hat. Es genügt, dass nach dem festgestellten Sachverhalt eine derartige Auswirkung im Bereich des Möglichen liegt. Infolge der fehlenden ziffernmässigen Feststellbarkeit der Auswirkung eines Verfahrensmangels ist nach den gesamten Umständen und grundsätzlich mit freier Kognition zu beurteilen, ob der gerügte Mangel das Abstimmungsergebnis beeinflusst haben könnte. Dabei ist insbesondere die Grösse des Stimmenunterschiedes, die Schwere des festgestellten Mangels und dessen Bedeutung im Rahmen der Abstimmung zu berücksichtigen. Erscheint die Möglichkeit, dass die Abstimmung ohne den Mangel anders ausgefallen wäre, nach den gesamten Umständen als derart gering, dass sie nicht mehr ernsthaft in Betracht fällt, so kann von der Aufhebung der Abstimmung abgesehen werden (<ref-ruling> E. 4.4 S. 301; <ref-ruling> E. 3.3 S. 110; <ref-ruling> E. 3.4 S. 296; je mit Hinweisen; vgl. zum Ganzen BGE 1C_174/2010 vom 14. Dezember 2010 E. 2).
2.3.3 Stellt das Bundesgericht im Vorfeld einer Abstimmung oder bei deren Durchführung Mängel fest, so hebt es den Urnengang nur auf, wenn die gerügten Unregelmässigkeiten erheblich sind und das Ergebnis beeinflusst haben könnten. Die Beschwerdeführenden müssen in einem solchen Fall allerdings nicht nachweisen, dass sich der Mangel auf das Ergebnis der Abstimmung entscheidend ausgewirkt hat. Es genügt, dass nach dem festgestellten Sachverhalt eine derartige Auswirkung im Bereich des Möglichen liegt. Infolge der fehlenden ziffernmässigen Feststellbarkeit der Auswirkung eines Verfahrensmangels ist nach den gesamten Umständen und grundsätzlich mit freier Kognition zu beurteilen, ob der gerügte Mangel das Abstimmungsergebnis beeinflusst haben könnte. Dabei ist insbesondere die Grösse des Stimmenunterschiedes, die Schwere des festgestellten Mangels und dessen Bedeutung im Rahmen der Abstimmung zu berücksichtigen. Erscheint die Möglichkeit, dass die Abstimmung ohne den Mangel anders ausgefallen wäre, nach den gesamten Umständen als derart gering, dass sie nicht mehr ernsthaft in Betracht fällt, so kann von der Aufhebung der Abstimmung abgesehen werden (<ref-ruling> E. 4.4 S. 301; <ref-ruling> E. 3.3 S. 110; <ref-ruling> E. 3.4 S. 296; je mit Hinweisen; vgl. zum Ganzen BGE 1C_174/2010 vom 14. Dezember 2010 E. 2).
2.4 2.4.1 Gemäss § 64 Abs. 1 des Gesetzes über die politischen Rechte vom 1. September 2003 im Kanton Zürich (GPR/ZH; LS 161) wird zu jeder Abstimmungsvorlage ein kurzer, sachlich gefasster und gut verständlicher "Beleuchtender Bericht" verfasst. Bei fakultativen Volksreferenden muss der Beleuchtende Bericht die Stellungnahme des Referendumskomitees enthalten (§ 64 Abs. 1 lit. c GPR/ZH). Der Beleuchtende Bericht wird in der Regel von der Exekutive verfasst (§ 64 Abs. 3 GPR/ZH).
2.4.2 Die kommunale Abstimmungszeitung zum Umbaukredit für die Anlaufstelle für Randständige an der Y._strasse enthält einen längeren Beleuchtenden Bericht, welcher die wesentlichen Aspekte der Vorlage erörtert. Nicht gefolgt werden kann der Argumentation der Beschwerdeführer, der Stadtrat habe mangels Erwähnung der auf dem in Frage stehenden Grundstück lastenden Dienstbarkeit für den Entscheid der Stimmbürger wichtige Elemente unterdrückt. Wie ausgeführt, muss die Behörde sich nicht mit jeder Einzelheit einer Vorlage befassen und nicht alle denkbaren Einwendungen, welche gegen eine Vorlage erhoben werden können, erwähnen (vgl. E. 2.3.2 hiervor). Die fragliche Dienstbarkeit zugunsten der beiden Nachbarsgrundstücke schreibt vor, dass auf dem Grundstück an der Y._strasse nicht mehr als zwei Häuser erstellt werden dürfen, welche unter sich einen Mindestabstand von 16,5 Meter aufweisen müssen. Dieser Mindestabstand zwischen den beiden seit langem bestehenden Gebäuden wird bereits heute nicht eingehalten, sondern beträgt bloss rund 12,5 Meter. Wie die Vorinstanz zutreffend betont, ändert sich mit der Abstimmungsvorlage an der Sach- und Rechtslage nichts. Mit dem Umbauprojekt bleiben die bisherigen Bauvolumen unverändert, und die konkrete Nutzung des Grundstücks bildet ohnehin nicht Gegenstand der Dienstbarkeit. Vor diesem Hintergrund kann nicht gesagt werden, dass ein Hinweis auf die bestehende Dienstbarkeit in den Abstimmungserläuterungen zwingend geboten gewesen wäre.
2.4.3 In der Abstimmungszeitung werden die für und gegen die Vorlage sprechenden Argumente dargelegt, indem der begründeten Abstimmungsempfehlung von Regierung und Parlament die Stellungnahme des Referendumskomitees gegenübergestellt wird. Wie die Vorinstanz allerdings zu Recht festhält, ist die Gestaltung der Abstimmungszeitung problematisch, da die Stellungnahme des Referendumskomitees in kleiner Schriftgrösse abgedruckt wurde. Eine Abstimmung ist jedoch, wie dargelegt, nur aufzuheben, wenn die gerügten Unregelmässigkeiten erheblich sind und das Ergebnis beeinflusst haben könnten, wobei insoweit namentlich die Grösse des Stimmenunterschieds und die Schwere des festgestellten Mangels zu berücksichtigen sind (vgl. E. 2.3.3 hiervor).
Die Voraussetzungen für eine Aufhebung sind vorliegend nicht erfüllt: Die Vorlage wurde mit rund 62 %, respektive 19'986 Ja-Stimmen gegen 12'210 Nein-Stimmen, sehr deutlich angenommen, und der festgestellte Mangel kann nicht als schwer qualifiziert werden, ist die Abstimmungsbotschaft doch einzig gestalterisch zu beanstanden. Inhaltlich hingegen wurde in der Abstimmungszeitung umfassend über die Vor- und Nachteile der Vorlage informiert, was den Stimmberechtigten eine objektive Beurteilung erlaubte. Die Tatsache, dass die Argumente der Beschwerdeführer verglichen mit dem Positionsbezug der Regierung in einer kleineren Schriftgrösse abgedruckt wurden, dürfte sich auf die Meinungsbildung der Stimmbürger kaum entscheidend ausgewirkt haben. Die Möglichkeit, dass die Abstimmung ohne diesen gestalterischen Mangel der Abstimmungsbotschaft anders ausgefallen wäre, das heisst, dass die Vorlage von einer Mehrheit des Stimmvolks abgelehnt worden wäre, erscheint nach den gesamten Umständen als derart gering, dass sie nicht ernsthaft in Betracht fällt.
3. Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Bei diesem Ausgang sind die Kosten des bundesgerichtlichen Verfahrens den Beschwerdeführern aufzuerlegen (<ref-law>). Der Stadt Winterthur ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, der Stadt und dem Bezirksrat Winterthur sowie dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, 4. Kammer, schriftlich mitgeteilt.
Lausanne, 7. Februar 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Fonjallaz Stohner