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.