Sachverhalt:
A. X._ erhob mit Schreiben vom 9. Dezember 2012 Strafklage gegen Y._. Er warf diesem im Wesentlichen vor, ihm ein Rechaud weggenommen zu haben. Er empfange als abgewiesener Asylsuchender in der Gemeinde Mels Nothilfe und benutze als Unterkunft einen ihm zur Verfügung gestellten Container. Am 5. Dezember 2011 habe er sein Rechaud nicht mehr im Container vorgefunden. Y._ habe bestätigt, dass er das Rechaud weggenommen habe. Dadurch habe dieser ihm einen Nachteil zugefügt, denn ohne Rechaud könne er sich nur ungenügend ernähren. Die Unterstützung von Fr. 8.--, die er pro Tag erhalte, reiche nicht aus, wenn man nicht die Gelegenheit habe, selbst zu kochen. Feuerpolizeiliche Gründe seien zudem nicht ausschlaggebend gewesen, dies habe der Gemeindepräsident schon bei früherer Gelegenheit festgestellt, als ein anderes Rechaud ebenfalls entfernt worden sei. Y._ meine vielmehr, dass er es den Nothilfeempfängern nicht zu bequem machen wolle.
Die Staatsanwaltschaft des Kantons St. Gallen übermittelte das Schreiben von X._ zur Durchführung eines Ermächtigungsverfahrens an die Anklagekammer des Kantons St. Gallen. Mit Entscheid vom 14. Februar 2012 entschied die Anklagekammer, gegen Y._ werde kein Strafverfahren eröffnet.
B. Mit Beschwerde vom 1. März 2012 an das Bundesgericht beantragt X._, der Entscheid der Anklagekammer sei aufzuheben und diese sei anzuweisen, das Strafverfahren zu eröffnen. Eventualiter sei die Sache zur Sachverhaltsergänzung an die Anklagekammer zurückzuweisen.
Die Anklagekammer hat auf eine Vernehmlassung verzichtet. Die Gemeinde Mels und Y._ beantragen, die Beschwerde sei abzuweisen und es sei ein Kostenvorschuss für die Gerichtsgebühr zu verlangen, zumal das Verhalten des Beschwerdeführers querulatorische Züge habe. Auf eine Parteientschädigung werde indessen verzichtet, weil der Beschwerdeführer von der Sozialhilfe abhängig sei und ausser zusätzlichen Kosten und Aufwänden nichts resultieren würde. Der Beschwerdeführer hält in seiner Stellungnahme dazu im Wesentlichen an seinen Anträgen und Rechtsauffassungen fest.

Erwägungen:
1. 1.1 Die Ermächtigung zur Strafverfolgung stellt eine Prozessvoraussetzung für das Strafverfahren dar, wird jedoch in einem davon getrennten Verwaltungsverfahren erteilt. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist deshalb das zutreffende Rechtsmittel (<ref-ruling> E. 1.3.1 S. 272 mit Hinweisen).
1.2 Gemäss Art. 17 Abs. 2 lit. b Satz 1 des Einführungsgesetzes des Kantons St. Gallen vom 3. August 2010 zur Schweizerischen Straf- und Jugendstrafprozessordnung (SGS 962.1; im Folgenden: EG-StPO) entscheidet die Anklagekammer über die Eröffnung des Strafverfahrens gegen Behördenmitglieder oder Mitarbeitende des Kantons und der Gemeinden wegen strafbarer Handlungen, die deren Amtsführung betreffen, soweit nicht der Kantonsrat zuständig ist. Im vorliegenden Fall entschied die Anklagekammer, es sei kein Strafverfahren zu eröffnen. Angesichts der Wortwahl in Art. 17 EG-StPO und im angefochtenen Entscheid ist klarzustellen, dass vorliegend erst die Ermächtigung zur Strafverfolgung in Frage steht. Der förmliche Entscheid über die Eröffnung oder die Nichtanhandnahme obliegt kraft ausdrücklicher bundesrechtlicher Regelung der Staatsanwaltschaft (Art. 309 und 310 StPO; <ref-ruling> E. 2.3 S. 277).
1.3 Angefochten ist ein Entscheid einer letzten kantonalen Instanz, der das Verfahren abschliesst (Art. 86 Abs. 1 lit. d und Art. 90 BGG). Eine Ausnahme von der Zulässigkeit der Beschwerde nach <ref-law> besteht nicht. Lit. e dieser Bestimmung, wonach Entscheide über die Verweigerung der Ermächtigung zur Strafverfolgung von Behördenmitgliedern oder von Bundespersonal von der Beschwerdemöglichkeit ausgenommen sind, ist nur auf die obersten Vollziehungs- und Gerichtsbehörden anwendbar, denn nur bei diesen dürfen politische Gesichtspunkte in den Entscheid einfliessen (<ref-ruling> E. 1.3.2 S. 272 f. mit Hinweis).
1.4 Zur Beschwerde ist nach <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a), durch den angefochtenen Entscheid oder Erlass besonders berührt ist (lit. b) und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (lit. c). Das schutzwürdige Interesse kann rechtlicher oder tatsächlicher Natur sein (<ref-ruling> E. 2.2 S. 290). Der Beschwerdeführer hat am Verfahren vor der Anklagekammer teilgenommen. Er hat durch das Verhalten, das Gegenstand des strafrechtlichen Vorwurfs bildet, einen Eingriff in sein Eigentum erlitten. Die Beschwerdelegitimation ist deshalb zu bejahen.
1.5 Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2. 2.1 Der Beschwerdeführer bringt vor, aufgrund der Beweislage sei klar, dass feuerpolizeiliche Gründe keine Rolle gespielt hätten, als ihm sein Rechaud weggenommen worden sei. Er verweist auf eine angebliche Äusserung des Gemeindepräsidenten und darauf, dass sein diesbezügliches Vorbringen in der Strafklage unbestritten geblieben sei. Er rügt, sein Anspruch auf rechtliches Gehör sei verletzt worden, weil er nie Gelegenheit gehabt habe, zum neuen Vorbringen der Gegenseite, welche das Gegenteil behaupte, Stellung zu nehmen (<ref-law>). Die Vorinstanz habe in dieser Hinsicht den Sachverhalt willkürlich festgestellt (<ref-law>).
2.2 Der Beschwerdeführer setzte sich in seiner Strafklage mit den Motiven, welche der Wegnahme des Rechauds möglicherweise zu Grunde lagen, ausführlich auseinander. Er stellte sich dabei auf den Standpunkt, dass feuerpolizeiliche Gründe nicht ausschlaggebend gewesen sein können. Wenn der Beschwerdegegner und die Gemeinde Mels in ihrer Vernehmlassung im vorinstanzlichen Verfahren den gegenteiligen Standpunkt einnahmen und behaupteten, die Sicherheit der Bewohner des Containers sei ausschlaggebend gewesen, so kann dabei kaum von einem neuen Vorbringen gesprochen werden. Der Beschwerdeführer hat sich nach dem Gesagten ja bereits vorgängig zu dieser Frage geäussert. Er vermag im Verfahren vor Bundesgericht denn auch nicht darzulegen, inwiefern er sich diesbezüglich noch weitergehend hätte äussern wollen. Eine Verletzung des rechtlichen Gehörs ist unter diesen Voraussetzungen zu verneinen.
2.3 Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Die Anklagekammer erwog, die Wegnahme des Rechauds sei aus feuerpolizeilichen Gründen und zur Sicherheit der Bewohner der Container erfolgt. Aus dem angefochtenen Entscheid geht jedoch nicht klar hervor, ob die Anklagekammer diesem Umstand rechtliche Bedeutung zuschreibt und, wenn ja, welche. Eine eigentliche Subsumtion in Bezug auf die im angefochtenen Entscheid erörterten Tatbestände der Sachentziehung (<ref-law>) und des Amtsmissbrauchs (<ref-law>) fehlt. Hinweise auf den möglichen Grund für die Wegnahme des Rechauds ergeben sich aus den Akten. Diese enthalten neben der erwähnten Stellungnahme des Beschwerdegegners und der Gemeinde Mels einen vom 18. Januar 2012 datierten Brief von Z._ an die Vorinstanz. Z._, die nach eigenen Angaben dem Beschwerdeführer unterstützend zur Seite stand und sich in diesem Rahmen offensichtlich auch an die Vorinstanz wandte, führte aus, sie habe mit dem Gemeindepräsidenten von Mels telefoniert und ihm das Anliegen der Bewohner des Containers unterbreitet, wenn nicht im Container, so doch wenigstens vor diesem kochen zu dürfen. Der Gemeindepräsident habe das Begehren abgelehnt und explizit gesagt, das Kochverbot sei nicht aus feuerpolizeilichen Gründen erlassen worden, sondern weil es sich hier um eine Notschlafstelle und nicht um eine Unterkunft handle. In seiner Stellungnahme vom 14. Mai 2012 zuhanden des Bundesgerichts weist der Beschwerdeführer zur Untermauerung seines Standpunkts darauf hin, dass das Rechaud elektronisch und nicht etwa gasbetrieben sei.
Zusammenfassend ist festzuhalten, dass die Vorinstanz ohne Begründung die Sichtweise des Beschwerdegegners und der Gemeinde Mels übernommen hat. Ob es dabei den Sachverhalt willkürlich oder sonst unter Verletzung von Bundesrecht festgestellt hat, kann indessen offenbleiben, wie sich aus den nachfolgenden Erwägungen ergibt.
3. 3.1 In der Sache selbst wird im angefochtenen Entscheid Folgendes ausgeführt: Der angezeigte Sachverhalt vermöge ein strafrechtliches Verhalten, namentlich in Bezug auf die Tatbestände der Sachentziehung und des Amtsmissbrauchs, nicht zu begründen. Die Wegnahme des Rechauds sei aus feuerpolizeilichen Gründen und zur Sicherheit der Bewohner der Container erfolgt. Das Rechaud sei im Werkhof der Gemeinde Mels eingelagert, wo es vom Anzeiger grundsätzlich abgeholt werden könne. Unter diesen Voraussetzungen könne aber nicht von einer erheblichen Nachteilszufügung im Sinne von <ref-law> gesprochen werden. Auch liege klar kein Missbrauch der Amtsgewalt gemäss <ref-law> vor. Ein hinreichender Tatverdacht im Sinne von <ref-law> (SR 312.0) bestehe nicht, weshalb keine Strafuntersuchung gegen den Angezeigten zu eröffnen sei.
3.2 Der Beschwerdeführer bringt in Ergänzung zu seiner Kritik an der Annahme einer feuerpolizeilichen Motivierung vor, das Rechaud sei ein besonders wichtiger Bestandteil seines Eigentums. Er erhalte täglich Fr. 8.-- Nothilfe. Mit diesem Betrag könne er sich keine bereits zubereiteten Speisen kaufen. Er sei deshalb auf eine Kochgelegenheit angewiesen. Die Anklagekammer nenne keinen Rechtfertigungsgrund für die Sachentziehung. Insbesondere gehe sie, und dies zu Recht, nicht davon aus, dass das Rechaud eine ernste, unmittelbare und nicht anders abwendbare Gefahr darstelle. Ausführungen zur Verhältnismässigkeit oder zum Ersatz für die Eigentumsbeschränkung fehlten im angefochtenen Entscheid.
3.3 Nach <ref-law> macht sich der Sachentziehung strafbar, wer dem Berechtigten ohne Aneignungsabsicht eine bewegliche Sache entzieht und ihm dadurch einen erheblichen Nachteil zufügt. Vorliegend ist unbestritten, dass das Rechaud dem Beschwerdeführer gehörte und der Beschwerdegegner es ihm wegnahm. Die Vorinstanz verneinte indessen das Tatbestandsmerkmal des erheblichen Nachteils, denn der Beschwerdeführer könne das Rechaud grundsätzlich im Werkhof der Gemeinde Mels abholen. Dass der Beschwerdeführer das Rechaud "grundsätzlich" im Werkhof abholen kann, ergibt sich aus der Vernehmlassung vom 13. Januar 2012 des Beschwerdegegners und der Gemeinde Mels im Rahmen des vorinstanzlichen Verfahrens. Unklar ist, in welchem Zeitpunkt dem Beschwerdeführer mitgeteilt wurde, wo sein Rechaud ist, zumal der Beschwerdegegner ihm dieses unbestritten bereits am 5. Dezember 2011 weggenommen hatte. Weiter fällt auf, dass laut der Vernehmlassung die Rückgabe nur unter der Bedingung erfolgt, dass er dieses "den Betreuern" zurückgibt.
Für eine Person, die täglich Fr. 8.-- Nothilfe erhält und in einem Container ohne Kochstelle untergebracht ist, kann die Wegnahme eines Rechauds einen erheblichen Nachteil im Sinne von <ref-law> bedeuten. Dies trifft auch dann zu, wenn sie nur einige wenige Tage auf diesen Gegenstand verzichten muss und man trotz der erwähnten Bedingung für die Rückgabe nicht von einem endgültigen Entzug des Gegenstands ausgeht. Auf der Grundlage des von der Anklagekammer festgestellten Sachverhalts kann nicht gesagt werden, der Tatbestand von <ref-law> sei klar nicht erfüllt. Darüber, wie es sich abschliessend damit verhält, ist im Rahmen eines Strafverfahrens zu entscheiden. Eine haltlose oder mutwillige Strafanzeige liegt nicht vor (<ref-ruling> E. 2.7.2 S. 279; <ref-ruling> E. 2c S. 352 mit Hinweisen). Indem die Anklagekammer die Ermächtigung zur Eröffnung eines Strafverfahrens verweigerte, verletzte sie <ref-law> i.V.m. <ref-law> (vgl. zur Publ. bestimmtes Urteil 1B_687/2011, 1B_689/2011 vom 27. März 2012 E. 4.1 f.; BGE 137 IV 219 E. 7.1 S. 226; je mit Hinweisen).
4. Die Beschwerde ist gutzuheissen und der angefochtene Entscheid aufzuheben. Die Ermächtigung zur Strafverfolgung des Beschwerdegegners wird erteilt (vgl. <ref-law>).
Die Gerichtskosten werden dem unterliegenden Beschwerdegegner auferlegt (<ref-law>). Der nicht anwaltlich vertretene Beschwerdeführer hat keinen Anspruch auf eine Parteientschädigung (Art. 68 Abs. 1 und 2 BGG; <ref-ruling> E. 4 S. 446 mit Hinweis). Sein Gesuch um unentgeltliche Rechtspflege wird bei diesem Verfahrenausgang gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der angefochtene Entscheid aufgehoben. Die Ermächtigung zur Strafverfolgung des Beschwerdegegners wird erteilt.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdegegner auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, der Gemeinde Mels, der Staatsanwaltschaft des Kantons St. Gallen, Untersuchungsamt Uznach, und der Anklagekammer des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 13. Juni 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold