Sachverhalt:
A. Der aus Indien stammende X._ reiste am 23. Dezember 2002 in die Schweiz ein, wo er um Asyl ersuchte. Nachdem sein Asylgesuch am 14. August 2003 abgewiesen worden war, tauchte er unter. Am 26. Juni 2006 heiratete er die in Solothurn wohnhafte Schweizer Bürgerin A._. Seit dem 1. September 2007 ist er als Wochenaufenthalter in Zürich gemeldet, wo er als Küchenhilfe in einem Restaurant arbeitet.
Am 15. Januar 2010 teilte der Vermieter der Liegenschaft B._strasse 148 in Solothurn den Einwohnerdiensten der Stadt Solothurn mit, er habe erfahren, dass seine Mieterin A._ mit einem Inder verheiratet sei, der nicht im Haus wohne. Der Einwohnerdienst gab den Ehegatten darauf Gelegenheit, zur aktuellen Wohnsituation Stellung zu nehmen, und X._ wurde in der Folge persönlich befragt.
B. Am 9. Mai (recte: Juni) 2010 verfügten die Einwohnerdienste der Stadt Solothurn, gestützt auf das Gemeindegesetz des Kantons Solothurn, X._s Wohnsitz befinde sich seit dem 1. September 2007 in der Stadt Zürich. X._ habe seiner persönlichen Meldepflicht nachzukommen und sich bei den Einwohnerdiensten der Stadt Solothurn innert 14 Tagen abzumelden. Gegen diese Verfügung rekurrierte X._ erfolglos bei der Beschwerdekommission Solothurn sowie beim Volkswirtschaftsdepartement des Kantons Solothurn. Mit Urteil vom 14. Oktober 2011 wies das Verwaltungsgericht des Kantons Solothurn X._s Beschwerde ebenfalls ab.
C. Mit Eingabe vom 17. November 2011 führt X._ beim Bundesgericht Beschwerde mit den Anträgen, der Entscheid der Einwohnerdienste vom 9. Mai (recte: Juni) 2010 der Stadt Solothurn sowie die vorinstanzlichen Entscheide aufzuheben und festzustellen, dass sich sein gesetzlicher Wohnsitz nach wie vor an der B._strasse 148 in 4500 Solothurn befinde.
Das Verwaltungsgericht des Kantons Solothurn und das Volkswirtschaftsdepartement des Kantons Solothurn schliessen auf Abweisung der Beschwerde. Die Stadt Solothurn beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei.
D. Mit Verfügung vom 21. Dezember 2011 hat der Abteilungspräsident das Gesuch um aufschiebende Wirkung der Beschwerde abgewiesen.

Erwägungen:
1. 1.1 Das angefochtene Urteil ist ein kantonal letztinstanzlicher Entscheid in einer Angelegenheit des öffentlichen Rechts, gegen den grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (Art. 82 lit. a und <ref-law>). Anfechtungsobjekt bildet jedoch ausschliesslich das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 14. Oktober 2011. Soweit mit dem Rechtsmittel die Aufhebung der Entscheide der unteren kantonalen Instanzen verlangt wird, kann darauf nicht eingetreten werden (Devolutiveffekt; vgl. <ref-law>; <ref-ruling> E. 1.4 S. 144 mit Hinweis).
1.2 Mit der Beschwerde können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Dabei prüft es, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 2.2.1 S. 389).
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, wie die Vorinstanz ihn festgestellt hat (<ref-law>). Es kann diesen bloss berichtigen oder ergänzen, falls er offensichtlich unrichtig oder in Verletzung wesentlicher Verfahrensrechte ermittelt worden ist (<ref-law>). Der Betroffene muss dartun, dass und inwiefern der festgestellte Sachverhalt in einem entscheidwesentlichen Punkt klar und eindeutig mangelhaft erscheint (vgl. Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; <ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3; 393 E. 7.1 S. 398; 462 E. 2.4 S. 466).
2. Die Schweizer Gemeinden haben ein Einwohnerregister zu führen, welches von jeder Person, die sich niedergelassen hat oder aufhält, mindestens die Daten zu den in Art. 6 des Bundesgesetzes vom 23. Juni 2006 über die Harmonisierung der Einwohnerregister und anderer amtlicher Personenregister (Registerharmonisierungsgesetz, RHG; SR 431.02) genannten Identifikatoren und Merkmale enthalten muss. Nach <ref-law> erlassen die Kantone die notwendigen Vorschriften, damit natürliche Personen sich innerhalb von 14 Tagen nach dem Umzug bei der für die Führung des Einwohnerregisters zuständigen Amtsstelle melden (lit. a) sowie die Meldepflichtigen wahrheitsgetreu Auskunft über die Daten nach Artikel 6 erteilen und, wenn erforderlich, ihre Angaben dokumentieren (lit. b).
Der Kanton Solothurn hat im Gemeindegesetz vom 16. Februar 1992 (GG; BGS 131.1) eine Regelung betreffend Einwohnerkontrolle getroffen. Nach § 3 Abs. 1 GG hat sich innert 14 Tagen anzumelden und seine Ausweispapiere zu hinterlegen, wer in einer Einwohnergemeinde Wohnsitz oder Aufenthalt begründet. Wer seinen Wohnsitz oder Aufenthalt aufgibt, hat sich innert 14 Tagen abzumelden (§ 3 Abs. 2 GG). Gemäss § 5 Abs. 1 GG richten sich Wohnsitz und Aufenthalt einer Person nach dem Zivilrecht. Nach <ref-law> befindet sich der Wohnsitz einer Person an dem Ort, wo sie sich mit der Absicht dauernden Verbleibens aufhält. Niemand kann an mehreren Orten zugleich seinen Wohnsitz haben (<ref-law>). Gemäss <ref-law> bleibt der einmal begründete Wohnsitz einer Person bis zum Erwerb eines neuen Wohnsitzes bestehen.
3. Der Beschwerdeführer macht zu Recht nicht geltend, das angewendete kantonale Recht verstosse gegen Bundesrecht. Er erhebt einzig Sachverhalts- und Beweiswürdigungsrügen.
3.1 Zur Hauptsache bringt der Beschwerdeführer vor, die Vorinstanzen hätten die Beweislastverteilung falsch vorgenommen. Wer sich auf das Bestehen eines bestimmten Wohnsitzes berufe, habe dies zu beweisen. Die Gegenpartei habe die Begründung eines neuen Wohnsitzes zu beweisen. Im vorliegenden Fall hätten die Einwohnerdienste behauptet, der Beschwerdeführer habe ab 1. September 2007 einen neuen Wohnsitz in der Stadt Zürich begründet. Dafür seien sie beweispflichtig.
Diese Ausführungen des Beschwerdeführers greifen zu kurz. Die Vorinstanz hat zu Recht ausgeführt, in Bezug auf die Feststellung des Wohnsitzes sei zu beachten, dass aufgrund von objektiven, äusseren Umständen auf innere Tatsachen, nämlich den Mittelpunkt der Lebensinteressen, geschlossen werden müsse. Daraus ergibt sich, dass nicht ein klarer Beweis geführt werden kann, sondern aufgrund von Indizien eine Gewichtung vorzunehmen ist (vgl. als Beispiele aus der steuerrechtlichen Praxis <ref-ruling> E. 4.2 S. 36; Urteil 2C_919/2011 vom 9. Februar 2012 E. 3.2). Dies übersieht der Beschwerdeführer, wenn er meint, die Behörden hätten rechtsgenüglich zu beweisen, dass sich sein Lebensmittelpunkt in Zürich befinde, und daraus implizit den Schluss zieht, er selbst habe keinen Nachweis für den behaupteten Wohnsitz in Solothurn zu leisten. Vielmehr obliegt es ihm darzutun, welche Indizien für einen Wohnsitz in Solothurn sprechen, nachdem die Behörden dargelegt haben, dass aus ihrer Sicht die Indizien für eine Wohnsitznahme in Zürich sprechen. Erst wenn sich aufgrund der Indizien sowohl für den einen wie auch für den anderen Ort kein Schluss auf den Wohnsitz ziehen lässt, kann eine Beweislastregelung in dem vom Beschwerdeführer genannten Sinn, d.h. im Ergebnis zugunsten des Weiterbestehens des bisherigen Wohnsitzes, Platz greifen.
3.2 Der Beschwerdeführer beanstandet sodann, dass die Namen der Auskunftspersonen im Bericht der Stadtpolizei Solothurn vom 17. März 2010 betreffend die Befragung der Nachbarn abgedeckt worden seien. Dies sei eine Verletzung des Akteneinsichtsrechts, welches aus dem Anspruch auf rechtliches Gehör i.S. von <ref-law> abgeleitet werde. Es sei nicht klar, ob und allenfalls wie lange die Auskunftspersonen an der fraglichen Adresse wohnen würden. Dem genannten Bericht könnten deshalb keine relevanten Informationen entnommen werden.
3.2.1 Das rechtliche Gehör gemäss <ref-law> dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (<ref-ruling> E. 3.2 S. 494; <ref-ruling> E. 2b S. 56; <ref-ruling> E. 4b S. 268, mit Hinweisen).
3.2.2 Es kann offenbleiben, ob die Abdeckung der Namen der Informanten in den Akten die Einsichtsrechte des Beschwerdeführers derart tangierten, dass von einer Verletzung des rechtlichen Gehörs auszugehen wäre, und ob diese in den vorinstanzlichen Verfahren nicht ohnehin als geheilt gelten müsste.
Soweit der Beschwerdeführer vorbringt, durch das Unkenntlichmachen von einzelnen Informationen in den Verfahrensakten sei die Feststellung des rechtserheblichen Sachverhalts beeinträchtigt, kann er daraus im bundesgerichtlichen Verfahren nichts zu seinen Gunsten ableiten. Wie bereits in E. 1.3 ausgeführt, ist bei der Erhebung einer Sachverhaltsrüge aufzuzeigen, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Vor Bundesgericht ist also von Bedeutung, ob die Kenntnis der nicht anonymisierten Informationen dem Beschwerdeführer weitere, entscheidende Vorbringen ermöglicht hätte. Entsprechend der aufgezeigten Substantiierungslast von <ref-law> wäre es an ihm gewesen, die Relevanz der Identität der Auskunftspersonen darzutun. Dieser prozessualen Obliegenheit ist der Beschwerdeführer indes nicht in genügendem Mass nachgekommen: Bereits vor der Vorinstanz machte er geltend, es sei nicht klar, seit wann die befragten Nachbarn in dem fraglichen Haus wohnten, weshalb deren Aussagen nicht relevant seien. Zudem sei es durchaus denkbar, dass die Nachbarn den Beschwerdeführer nicht kennen würden, da dieser sich nur an den Wochenenden und teils unter der Woche in der ehelichen Wohnung aufhalte. Die Vorinstanz hielt diesbezüglich fest, es seien nur wenige Personen durch die Polizei befragt worden und es sei tatsächlich nicht bekannt, wie lange diese schon in derselben Liegenschaft wohnten wie Frau A._. Trotzdem erscheine es sonderbar, dass keiner der Befragten den Beschwerdeführer je bei dessen Ehefrau gesehen habe, wenn dieser fast an jedem Wochenende dort sein wolle und manchmal auch unter der Woche. Vor Bundesgericht legt der Beschwerdeführer nicht dar, inwiefern ihm die Kenntnis der Namen der befragten Nachbarn bezüglich der vorinstanzlichen Feststellungen weitere, entscheidende Vorbringen ermöglicht hätten. Relevant erscheint in diesem Zusammenhang vielmehr, dass der Beschwerdeführer selbst keine unabhängigen Personen benennt, welche seine Anwesenheiten in irgendeiner Weise bestätigen könnten.
3.3 Der Beschwerdeführer beanstandet im Weiteren die von der Vorinstanz vorgenommene Würdigung der Aussagen des Rapporterstatters der Stadtpolizei Zürich. Er ist der Auffassung, dessen Wahrnehmungen hätten nicht in den Entscheid miteinbezogen werden dürfen und würden kein taugliches Indiz bilden.
Dem kann nicht gefolgt werden. Die Vorinstanz hat berücksichtigt, dass die genannten Aussagen nur die subjektive Wahrnehmung des Rapporterstatters aufzeigen würden und deshalb nicht zu stark gewichtet werden dürften. Es ist nicht ersichtlich, inwiefern die Vorinstanz diesen Aussagen ein zu starkes Gewicht beigemessen hätte oder inwiefern die Aussagen überhaupt nicht relevant wären. Allein aus dem Umstand, dass der Rapporterstatter für die Dienststelle für Ausländerbelange arbeitet, lässt sich jedenfalls nicht schliessen, dieser sei als Auskunftsperson befangen.
3.4 Der Beschwerdeführer rügt sodann die Beweiswürdigung der Vorinstanz in Bezug auf die eingereichten Bahnbillette und deren Feststellung, es frage sich, weshalb er nach dem 12. Juni 2010 keine weiteren Bahnbillette mehr gesammelt und eingereicht habe. Zur Begründung dieser Rüge beschränkt er sich jedoch einerseits auf die Feststellung, es sei nicht seine Aufgabe, den Wohnsitz in Solothurn zu beweisen. Wie bereits dargelegt, greift diese Auffassung zu kurz (vgl. E. 3.1). Andererseits führt er aus, er habe aufgehört, weitere Billette einzureichen, weil man ihm dann vorgeworfen hätte, er würde die Beweise wegen des laufenden Verfahrens sammeln, um einen Wohnsitz in Solothurn zu beweisen. Diese Begründung erscheint angesichts des Umstands, dass der Beschwerdeführer in einem laufenden Verfahren betreffend seinen Wohnsitz stand und ihm bewusst war, dass alle Indizien relevant sind, als abwegig. Auf jeden Fall kann sie nichts an der vorinstanzlichen Beweiswürdigung ändern.
3.5 Sodann macht der Beschwerdeführer betreffend weitere von der Vorinstanz festgestellte Indizien geltend, es gehe vorliegend nicht um die Frage, ob eine Scheinehe vorliege. Es treffe auch nicht zu, dass er schlecht Deutsch spreche. Und schliesslich sei es gerichtsnotorisch, dass der Arbeitsmarkt im Bereich des Gastgewerbes in Zürich bedeutend erfolgsversprechender sei als in Solothurn.
Mit diesen Ausführungen vermag der Beschwerdeführer die vorinstanzliche Beweiswürdigung nicht zu entkräften. Die Vorinstanz durfte selbstverständlich Überlegungen zum Verhältnis der Eheleute in ihre Abwägungen einbeziehen, ergeben sich doch daraus zweifellos Hinweise auf den Lebensmittelpunkt. Die Ausführung, wonach es dem Anwalt möglich sei, mit dem Beschwerdeführer ohne Dolmetscher zu verkehren, vermag die vorinstanzliche Feststellung betreffend Sprachkenntnisse, welche sich auf den Bericht der Stadtpolizei Zürich vom 3. März 2010 abstützt, nicht zu widerlegen. Sodann ist nicht ersichtlich, inwiefern die vorinstanzliche Ausführung unrichtig wäre, es sei nicht glaubwürdig, dass der Beschwerdeführer während der gesamten Ehedauer von bereits mehr als fünf Jahren keine Anstellung als Küchenhilfe oder ähnliches in der Nähe von Solothurn gefunden haben solle. Die vom Beschwerdeführer in diesem Zusammenhang neu eingereichten Beweismittel sind im Übrigen als unzulässige Noven unbeachtlich (<ref-law>), hätte sie der Beschwerdeführer doch bereits im vorinstanzlichen Verfahren einreichen können. Dazu hätte er auch Veranlassung gehabt, wurde doch bereits im erstinstanzlichen Verfahren diskutiert, es sei nicht nachvollziehbar, dass er es vorziehe, in Zürich zu arbeiten statt in der Nähe der ehelichen Wohnung.
4. Die Beschwerde erweist sich nach dem Gesagten als unbegründet und ist abzuweisen.
4.1 Der Beschwerdeführer hat darum ersucht, von der Auferlegung von Verfahrenskosten abzusehen und ihm einen unentgeltlichen Rechtsbeistand beizugeben. Angesichts der sorgfältigen und eingehenden Begründung der Vorinstanz im angefochtenen Entscheid und des Umstands, dass sich die Beschwerde in Sachverhalts- und Beweiswürdigungsrügen erschöpft, welche offensichtlich untauglich sind, ist festzustellen, dass die Eingabe von vornherein keine Aussichten auf Erfolg hatte. Dem Begehren kann daher wegen Aussichtslosigkeit der Beschwerde nicht entsprochen werden (<ref-law>).
4.2 Die Kosten des bundesgerichtlichen Verfahrens sind dem Beschwerdeführer als unterliegender Partei zu auferlegen (<ref-law>); bei der Bemessung der Gerichtsgebühr kann seiner finanziellen Lage Rechnung getragen werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 3. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Genner