Sachverhalt: A. Am 23. März 2011 erstattete die Y._GmbH gegen X._ Strafanzeige wegen Sachbeschädigung. Die Staatsanwaltschaft Basel-Landschaft eröffnete ein Strafverfahren, stellte dieses jedoch mit Verfügung vom 11. August 2011 wieder ein. Zur Begründung führte sie aus, X._ werde vorgeworfen, am 23. März 2011 um 16:15 Uhr an der Gartenstrasse 12 in Binningen den dort geparkten Personenwagen der Y._GmbH an der Heckklappe mit einer Plastikauszugsleine zerkratzt zu haben. Dabei sei ein Sachschaden in der Höhe von Fr. 1'142.30 (zzgl. 8 % MwSt) entstanden. Zum erwähnten Zeitpunkt sei X._ von einem Spaziergang nach Hause gekommen, wobei er einen Hund an einer Plastikauszugsleine geführt habe. Er sei am Heck des Personenwagens vorbeigegangen. Auf dessen Führersitz sei ein Angestellter der Y._GmbH gesessen und habe einen Arbeitsrapport ausgefüllt. Der Angestellte habe später ausgesagt, er habe ein metallisches Geräusch wahrgenommen, jedoch nichts gesehen und sei erst rund zwei, drei Minuten später ausgestiegen. Er habe an der Hecktüre einen Schaden bemerkt, von dem er angenommen habe, er stamme von X._. Die Staatsanwaltschaft kam zum Schluss, da der Beschuldigte den Vorwurf bestreite und dieser ihm nicht mit hinreichender Sicherheit nachgewiesen werden könne, sei das Verfahren einzustellen. Die Verfahrenskosten seien auf die Staatskasse zu nehmen (Ziff. 3 der Verfügung) und der beschuldigten Person sei keine Entschädigung oder Genugtuung auszurichten (Ziff. 4 der Verfügung). Am 22. August 2011 erhob X._ Beschwerde beim Kantonsgericht Basel-Landschaft und beantragte, es sei Ziff. 4 der Einstellungsverfügung aufzuheben und es sei ihm eine Entschädigung von Fr. 2'880.45 auszurichten. Mit Beschluss vom 1. November 2011 wies das Kantonsgericht die Beschwerde ab. B. Mit Beschwerde in Strafsachen an das Bundesgericht vom 13. Dezember 2011 beantragt X._, der Beschluss des Kantonsgerichts sei aufzuheben. Es sei ihm für das Verfahren vor der Staatsanwaltschaft eine Entschädigung von Fr. 2'880.45 und für das Verfahren vor dem Kantonsgericht eine solche von Fr. 2'000.-- auszurichten. Das Kantonsgericht beantragt die Abweisung der Beschwerde. Die Y._GmbH und die Staatsanwaltschaft haben sich nicht vernehmen lassen.