Sachverhalt:
A. Am 20. April 2010 reichte die X._ GmbH, vertreten durch Y._ und B._, gegen A._ eine Strafklage wegen Diebstahls ein. Y._ gab zu Protokoll, A._ habe im Januar 2009 im Auftrag und auf Kosten der Skischule eine Videokamera gekauft. Die Kamera habe er später als Pfand gegenüber der Skischule verwendet, da er der Auffassung gewesen sei, diese schulde ihm noch Geld.
Die Staatsanwaltschaft des Kantons Wallis verfügte am 22. August 2011, das Strafverfahren werde nicht anhand genommen. Zur Begründung führte sie aus, A._ sei im Januar 2010 von Y._ fristlos entlassen und gleichzeitig aufgefordert worden, die Videokamera auszuhändigen. Da Y._ jedoch am 12. Januar 2010 nicht wie vereinbart erschienen sei, habe A._ die Kamera wieder nach Hause genommen und dort aufbewahrt. Auf eine entsprechende Aufforderung der Polizei hin habe A._ die Videokamera umgehend auf dem Polizeiposten abgegeben. Obwohl Y._ von der Polizei mehrmals aufgefordert worden sei, die Kamera dort abzuholen, habe er sich geweigert, die Videokamera in Empfang zu nehmen. Durch sein Verhalten habe A._ weder den Tatbestand des Diebstahls noch der Veruntreuung erfüllt.
Eine von Y._ gegen die Nichtanhandnahmeverfügung erhobene Beschwerde wies das Kantonsgericht Wallis mit Verfügung vom 18. April 2012 ab, soweit es darauf eintrat. Zur Begründung führte es aus, es sei die X._ GmbH gewesen, die Strafanzeige eingereicht habe, und nur sie sei in ihrem Vermögen betroffen. Y._ fehle dagegen die Legitimation zur Beschwerde in eigenem Namen. Zudem sei die Beschwerde ohnehin abzuweisen, da der Beschuldigte weder die Absicht der ungerechtfertigten Bereicherung noch der Enteignung gehabt habe.
B. Mit Beschwerde in Strafsachen vom 21. Mai 2012 beantragen die X._ GmbH und Y._, der Entscheid des Kantonsgerichts sei aufzuheben und es sei eine Strafuntersuchung durchzuführen.
Das Kantonsgericht und die Staatsanwaltschaft haben auf eine Vernehmlassung verzichtet. Der Beschwerdegegner beantragt die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Der angefochtene Entscheid betrifft die Nichtanhandnahme einer Strafuntersuchung. Dagegen ist die Beschwerde in Strafsachen nach <ref-law> gegeben. Der Beschwerdeführer 2 hat am Verfahren vor dem Kantonsgericht teilgenommen, nicht hingegen die Beschwerdeführerin 1 (vgl. <ref-law>). Gemeinsam machen sie geltend, dieser Umstand sei letztlich auf einen Fehler der Staatsanwaltschaft zurückzuführen. Das Kantonsgericht habe gegen Art. 5 Abs. 3, Art. 9, Art. 29 Abs. 1 und Art. 29a BV verstossen, indem es die Beschwerdelegitimation verneint habe. Wie es sich damit und mit der Beschwerdelegitimation im bundesgerichtlichen Verfahren verhält, kann offen bleiben. Aus den nachfolgenden Erwägungen ergibt sich, dass die Beschwerde ohnehin abzuweisen ist, soweit darauf eingetreten werden kann.
1.2 Materiell zu beurteilen sind von vornherein nur jene Rügen, die sich auf den angefochtenen Entscheid beziehen (vgl. <ref-law>). Dies trifft nicht zu für die sinngemäss erhobene Forderung der Beschwerdeführer, es sei ein Strafverfahren wegen Betäubungsmittelkonsums durchzuführen. Weder die Nichtanhandnahmeverfügung vom 22. August 2011 noch der angefochtene Entscheid betrifft Betäubungsmitteldelikte. Dasselbe gilt für die Rüge, es sei auf die Veruntreuung von Kundengeldern nicht eingegangen worden. Auch dieser Vorwurf wurde in der Nichtanhandnahmeverfügung und im angefochtenen Entscheid nicht behandelt. Im Übrigen hatte zur Erörterung dieser Frage weder die Strafklage vom 20. April 2010 noch die Beschwerde an die Vorinstanz Anlass gegeben. Darauf ist nicht einzutreten.
2. 2.1 Die Beschwerdeführer rügen eine Verletzung von <ref-law>. Der Zeuge C._ habe in seiner Zeugenaussage bestätigt, dass der Beschwerdegegner die Videokamera als Druckmittel habe zurückbehalten wollen.
2.2 Bei der Frage, ob ein Strafverfahren über eine Nichtanhandnahme oder eine (definitive) Verfahrenseinstellung durch die Strafverfolgungsbehörde erledigt werden kann, gilt im schweizerischen Strafprozessrecht der Grundsatz "in dubio pro duriore". Dieser Grundsatz fliesst aus dem Legalitätsprinzip (<ref-law> und <ref-law> i.V.m. Art. 309 Abs. 1, Art. 319 Abs. 1 und Art. 324 Abs. 1 StPO; zur amtlichen Publikation bestimmtes Urteil 1B_687/2011 vom 27. März 2012 E. 4.2). Er bedeutet, dass eine Nichtanhandnahme oder Einstellung durch die Staatsanwaltschaft grundsätzlich nur bei klarer Straflosigkeit bzw. offensichtlich fehlenden Prozessvoraussetzungen angeordnet werden darf. Bei der Beurteilung dieser Frage verfügen die Staatsanwaltschaft und die Vorinstanz über einen gewissen Spielraum, den das Bundesgericht mit Zurückhaltung überprüft. Hingegen ist (sofern die Erledigung mit einem Strafbefehl nicht in Frage kommt) Anklage zu erheben, wenn eine Verurteilung wahrscheinlicher erscheint als ein Freispruch (vorerwähntes Urteil 1B_687/2011 vom 27. März 2012 E. 4.1.1; <ref-ruling> E. 7.1-7.2 S. 226 f.; je mit Hinweisen). Falls sich die Wahrscheinlichkeiten eines Freispruchs oder einer Verurteilung in etwa die Waage halten, drängt sich in der Regel, insbesondere bei schweren Delikten, ebenfalls eine Anklageerhebung auf (Urteil 1B_687/2011 vom 27. März 2012 E. 4.1.2 mit Hinweis).
2.3 Das Kantonsgericht begründete seinen Entscheid damit, dass es an der Absicht der ungerechtfertigten Bereicherung und der Absicht der Enteignung fehle. Selbst der Beschwerdeführer 2 gehe davon aus, dass der Beschwerdegegner die Kamera bloss als Pfand verwenden wollte und nicht beabsichtigte, die Skischule als Eigentümerin dauerhaft zu enteignen. Die Lohnforderung von ca. Fr. 19'000.--, welche der Beschwerdegegner geltend mache, übersteige den Wert der Kamera.
2.4 Die Beschwerdeführer und die Vorinstanz gehen übereinstimmend davon aus, dass der Beschwerdegegner die Videokamera als "Druckmittel" bzw. als Pfand zurückbehalten wollte. Weiter ist unbestritten, dass der Beschwerdegegner eine ausstehende Lohnforderung zu haben glaubt, auch wenn die Beschwerdeführer deren Bestand in Abrede stellen.
Vor diesem Hintergrund ist eine Absicht unrechtmässiger Bereicherung zu verneinen. Das Bundesgericht hat in einem auch von der Vorinstanz angeführten Urteil dargelegt, dass diesbezüglich nicht der objektive Bestand der Forderung, sondern die Vorstellung des Täters ausschlaggebend ist (<ref-ruling> E. 3a S. 35 mit Hinweisen). Auch wenn diese Vorstellung falsch und dies der Fahrlässigkeit des Beschwerdegegners zuzuschreiben wäre, änderte sich an der strafrechtlichen Beurteilung nichts. Gemäss <ref-law> ist der einem Sachverhaltsirrtum unterlegene Täter wegen Fahrlässigkeit strafbar, sofern er den Irrtum bei pflichtgemässer Vorsicht hätte vermeiden können und sofern die fahrlässige Begehung der Tat mit Strafe bedroht ist. Die Tatbestände der Veruntreuung und des Diebstahls stellen jedoch die fahrlässige Begehung nicht unter Strafe. Die Beurteilung der Vorinstanz, wonach klarerweise weder eine Veruntreuung noch ein Diebstahl vorliegt, ist deshalb nicht zu beanstanden. Die Rüge der Beschwerdeführer ist unbegründet.
3. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang tragen die Beschwerdeführer die Gerichtskosten (<ref-law>). Sie haben dem obsiegenden, anwaltlich vertretenen Beschwerdegegner eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Staatsanwaltschaft des Kantons Wallis und der Kantonsgerichts des Kantons Wallis, Strafkammer, schriftlich mitgeteilt.
Lausanne, 6. August 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold