Sachverhalt: A. A.a X._ sandte am 6. Oktober 2008 ein Paket mit einer grösseren Anzahl von Briefmarken, Postkarten und Umschlägen zur Stempelung an die Philateliestelle der Schweizerischen Post in Bern. Dort wurde festgestellt, dass es sich bei 115 dieser Wertzeichen um nachgemachte Briefmarken "Weltpostkongress Genf" mit einem Nominalwert von Fr. 1.30 handelte. Die Markenbögen mit den unechten Briefmarken waren an diesem Kongress vor Ort mit einem Laserdrucker ausgedruckt und abgegeben worden. Am 4. Dezember 2008 erstattete die Schweizerische Post Strafanzeige gegen X._ wegen Fälschung amtlicher Wertzeichen. A.b Die Staatsanwaltschaft Limmattal/Albis stellte die Untersuchung mit Verfügung vom 23. Juli 2009 ein, auferlegte X._ indessen die Kosten der Untersuchung. Zudem ordnete die Staatsanwaltschaft die Einziehung und Vernichtung der Briefmarken an. B. X._ stellte beim Bezirksgericht Horgen ein Begehren um gerichtliche Beurteilung des Entscheids über die Kosten- und Entschädigungsregelung sowie der Einziehung. Der Einzelrichter wies die Begehren ab. X._ wandte sich mit einem Rekurs an das Obergericht des Kantons Zürich. Das Obergericht hiess den Rekurs insoweit gut, als es die Kosten der Strafuntersuchung auf die Staatskasse nahm. Es sprach X._ indessen keine Entschädigung zu. C. X._ führt Beschwerde in Strafsachen ans Bundesgericht. Er beantragt, das Bundesgericht habe zu klären, wie der Status der Briefmarken sei (Antrag 1). Zudem seien alle bisherigen Verfügungen und Beschlüsse sowie die Beschlagnahme der Briefmarken aufzuheben (Anträge 2 und 3) und der aufgelaufene Schaden vollumfänglich zu ersetzen (Antrag 4). Die Post soll schliesslich angewiesen werden, sämtliche ihr eingelieferten Briefmarken entsprechend dem Postverkehrsgesetz zu bearbeiten (Antrag 5). X._ macht unter "Persönliches" geltend, er sei bedürftig. Diese Ausführungen sind als Gesuch um unentgeltliche Rechtspflege entgegenzunehmen. D. Die Vorinstanz sowie die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung. 