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.

Das Bundesgericht zieht in Erwägung:
1. Vor Bundesgericht sind nach dem vorinstanzlichen Entscheid nur noch die Frage der Einziehung der Briefmarken (Antrag 3) sowie das Absehen von einer Entschädigung (Antrag 4) Gegenstand des Verfahrens. Soweit sich der Beschwerdeführer nicht mit diesen Fragen befasst, ist darauf nicht einzutreten. Ebensowenig ist auf unzulässige Begehren (siehe Anträge 1, 2 und 5) einzutreten.
2. 2.1 Der Beschwerdeführer wendet sich gegen die Einziehung der in Frage stehenden Briefmarken, welche die Post von Qatar als Werbegeschenk den Delegierten und Journalisten, die am Weltpostkongress teilnahmen, zukommen liess. Er habe sämtliche Briefmarkenbögen im Rahmen des Kongresses unentgeltlich erhalten oder käuflich von denjenigen Delegierten erworben, die ihr Geschenk nicht nach Hause nehmen wollten. Die Beschlagnahme und Vernichtung füge ihm einen direkten finanziellen Schaden zu. Es gebe keinen rechtlichen Grund, warum sein Eigentum enteignet und eingezogen werde, zumal die Schweizerische Post ihre anfängliche Intervention gegen die Ausdrucke zurückgezogen und gar "aktiv die Verteilung goutiert" habe, indem sie die Markenbögen am Kongress durch ihre Mitarbeiter austeilen liess (Beschwerde, S. 9).
2.2 Die Vorinstanz hält fest, es sei nicht anzunehmen, dass die Schweizerische Post die Herstellung von Schweizerischen Briefmarken auf einem Laserdrucker anlässlich des Weltpostkongresses autorisiert habe, weshalb die Produktion der Bögen ein unberechtigtes Nachahmen von Schweizerischen Briefmarken dargestellt habe (angefochtener Entscheid S. 6). Die Vorinstanz bestätigt unter Hinweis auf die Ausführungen der ersten Instanz die Einziehung. Die eingezogenen Briefmarken würden eine Verwechslungsgefahr schaffen, da sie das gleiche Sujet wie echte Briefmarken aufwiesen. Zwar könnten sie mit einem Stempel als unecht markiert werden. Dann hätten sie indessen keinen Sammlerwert mehr. Somit sei eine legitime Verwendung nicht möglich, weshalb sie zu vernichten seien (angefochtenes Urteil, S. 11).
2.3 Gemäss <ref-law> werden unter anderem falsche oder verfälschte amtliche Wertzeichen eingezogen und unbrauchbar gemacht oder vernichtet. Dasselbe gilt gemäss Abs. 2 auch, wenn die amtlichen Wertzeichen ohne Fälschungsabsicht wiedergegeben, nachgeahmt oder hergestellt werden.
Entgegen der Ansicht des Beschwerdeführers (Beschwerde, S. 3 f.) stellen von der Schweizerischen Post herausgegebene Briefmarken amtliche Wertzeichen dar. Gemäss Art. 22 Abs. 1 des Postgesetzes (PG) vom 30. April 1997 (SR 783.0) übernimmt die Post die Rechte und Pflichten der PTT-Betriebe aus den öffentlich-rechtlichen Rechtsverhältnissen, die gestützt auf das Postverkehrsgesetz vom 2. Oktober 1924 begründet worden sind. Art. 37 Abs. 1 der Postverordnung (VPG) vom 26. November 2003 (SR 783.01), der gegenüber Art. 9 der Postverordnung vom 29. Oktober 1997 (AS 1997 2461) unverändert blieb, verleiht der Post das Recht, Postwertzeichen herauszugeben und dabei auf den Wertzeichen den Aufdruck «Helvetia» zu verwenden. Im Schrifttum wird die Eigenschaft der Briefmarken als amtliche Wertzeichen ebenfalls geteilt (vgl. MARCEL ALEXANDER NIGGLI, Kommentar zum schweizerischen Strafrecht, Band 6a, 2000, Art. 245 N 29; CHRISTIANE LENTJES MEILI/STEFAN KELLER, BSK StGB II, Art. 245 N. 12 f.). Briefmarken können daher der Einziehung gemäss <ref-law> unterliegen.
2.4 Dass die Briefmarkenbögen die von der Vorinstanz ins Feld geführte Verwechslungsgefahr begründeten, wird vom Beschwerdeführer nicht in Abrede gestellt. Es ist denn auch nicht ersichtlich, dass und inwieweit die auf <ref-law> beruhende Einziehung gegen das schweizerische Recht im Sinne von <ref-law> verstossen könnte.
2.5 Der Beschwerdeführer wendet sich neben der Einziehung insbesondere auch gegen die Vernichtung der Briefmarkenbögen, zumal ihm die Beschlagnahme und Vernichtung einen direkten finanziellen Schaden zufüge. Das Bundesgericht führte in einem ähnlich gelagerten Fall betreffend Einziehung einer Probeprägung eines Goldvrenelis aus, dass dieses dem Berechtigten - selbst wenn dies der Täter sei - wieder herausgegeben werden könne, sofern der eingezogene Gegenstand in sicherer Weise unbrauchbar gemacht und dadurch der Sicherungszweck der Einziehung ebenfalls erfüllt werden könne und die Sache für ihn noch einen Wert habe (<ref-ruling> E. 3b) Das Unbrauchbarmachen habe in einer Weise zu geschehen, die eine spätere Verwendung (als echt) unmöglich mache. Erst wenn dies nicht möglich sei, komme eine Vernichtung in Frage. Dies ergebe sich aus dem Grundsatz der Verhältnismässigkeit (a.a.O. E. 2f).
2.6 Die Vorinstanz räumt ein, dass die beschlagnahmten Marken mit einem Stempel als unecht markiert werden könnten, um die Verwechslungsgefahr mit echten Marken zu beseitigen. Sie erwägt weiter, dass die Marken diesfalls jedoch keinen Sammlerwert mehr hätten und dadurch eine legitime Verwendung wegfalle. Weshalb dies der Fall sein sollte, begründet die Vorinstanz nicht.
Dies entspricht auch nicht der Realität. Briefmarkenhändler bewerten nicht nur offiziell herausgegebene Wertzeichen, sondern versehen auch sogenannte Abarten, die auf einen Fehldruck oder einen Plattenfehler zurückzuführen sind, und etwa in falscher Farbe, auf abweichendem Papier oder mit anderem Wasserzeichen gedruckt worden sind, mit einem Preis. Dieser Preis ist aufgrund der Seltenheit von Abarten regelmässig wesentlich höher als derjenige für ein fehlerloses Wertzeichen (vgl. etwa CURT NICOLAUS FERNAU, Briefmarken, 2. Aufl. 1976, S. 30; SIEGFRIED SCHMITZ, Briefmarken sammeln, 1976, S. 43). Zu unterscheiden von diesen echten Abarten sind Druckzufälligkeiten, die während der Markenherstellung entstehen (FERNAU, a.a.O., S. 56 ff.). Diese stellen Fehler beim Druckvorgang dar. Die entsprechenden Bögen bzw. Marken sollten eigentlich als Makulatur aussortiert werden, gelangen jedoch trotzdem immer wieder in den Vertrieb. Die Preise hierfür liegen in der Regel deutlich tiefer als für echte Abarten. Wertlos sind diese Druckzufälligkeiten aber nicht. Auch die vorliegend in Frage stehenden, mittels Laserdrucker hergestellten Briefmarken, können durchaus einen Sammlerwert aufweisen, worauf auch der Beschwerdeführer an verschiedenen Stellen seiner Beschwerde hinweist (vgl. S. 6 f. und S. 8 f.). Dies gilt auch (oder gerade), wenn die Briefmarken von offizieller Stelle mit einem Ungültigkeitsvermerk entwertet werden.
2.7 Das Bundesgericht erkannte im <ref-ruling>, dass die Nichtwiederaushändigung der eingezogenen und unbrauchbar gemachten Probeprägung eines Goldvrenelis als unverhältnismässig und damit bundesrechtswidrig ist, da neben der Verwechslungsgefahr keine (anderen) Gründe geltend gemacht wurden, die einer Rückgabe der unbrauchbar gemachten Münze entgegenstehen könnten bzw. deren Zurückbehaltung als verhältnismässig erscheinen liessen.
Im vorliegenden Fall erweist sich die Nichtherausgabe der eingezogenen und unbrauchbar gemachten Briefmarken gleichermassen als unverhältnismässig. Durch das Unbrauchbarmachen wird eine Verwechslungsgefahr wirkungsvoll verhindert. Eine Vernichtung der Briefmarken bedarf es hierfür nicht. Die eingezogenen Briefmarken sind daher dem Beschwerdeführer - nach erfolgter Unbrauchbarmachung - wieder auszuhändigen.
2.8 In Bezug auf die Entschädigung hat es der Beschwerdeführer nach der Darstellung der Vorinstanz unterlassen, seine Forderungen zu substanziieren. Seine diesbezüglichen Ausführungen vor Bundesgericht (vgl. Beschwerde, S. 9 "Aufgelaufener Schaden") vermögen nicht aufzuzeigen, dass die Feststellung der Vorinstanz, er habe seine Forderung nicht substanziiert, gegen das schweizerische Recht im Sinne von <ref-law> verstossen könnte. Für die rechtmässig eingezogenen Briefmarken besteht im Übrigen - wie die Vorinstanz zu Recht ausführt - kein Entschädigungsanspruch. In Bezug auf die Entschädigungsforderungen ist daher auf die Beschwerde nicht einzutreten.
3. Die Beschwerde ist gutzuheissen, soweit darauf einzutreten ist. Der angefochtene Beschluss des Obergerichts des Kantons Zürich vom 8. März 2010 ist aufzuheben und die Sache zur Unbrauchbarmachung und anschliessenden Wiederaushändigung der eingezogenen Briefmarken an die Vorinstanz zurückzuweisen.
Da der Beschwerdeführer obsiegt, wird sein Gesuch um unentgeltliche Rechtspflege gegenstandslos (Art. 64 Abs. 1 und 2 BGG). Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 i.V.m. Abs. 4 BGG). Der Beschwerdeführer war nicht anwaltlich vertreten. Besondere Verhältnisse oder Auslagen weist er nicht nach. Eine Entschädigung rechtfertigt sich daher nicht (Art. 68 Abs. 1 und 2 BGG; <ref-ruling> E. 6b).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Der angefochtene Beschluss des Obergerichts des Kantons Zürich vom 8. März 2010 wird aufgehoben und die Sache zur Unbrauchbarmachung und anschliessenden Wiederaushändigung der eingezogenen Briefmarken an die Vorinstanz zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben und keine Entschädigungen zugesprochen.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 14. Juli 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Schneider Keller