Sachverhalt: A. Y._ stellte am 30. April 2012 Strafantrag gegen ihren ehemaligen Lebensgefährten X._ wegen Hausfriedensbruchs und Diebstahls respektive Sachentziehung. Mit Nichtanhandnahmeverfügung vom 16. August 2012 stellte die Staatsanwaltschaft des Kantons Bern das Verfahren wegen Hausfriedensbruchs ein und kündigte in Ziffer 4 des Dispositivs die Einleitung eines Strafbefehlverfahrens wegen Diebstahls an. Mit Strafbefehl vom 21. August 2012 sprach sie gegen X._ eine bedingte Geldstrafe von Fr. 100.-- sowie eine Verbindungsbusse von Fr. 250.-- aus und auferlegte ihm die Verfahrenskosten. B. X._ holte weder die Nichtanhandnahmeverfügung noch den Strafbefehl, die ihm per Gerichtsurkunde zugestellt worden waren, innert Frist bei der Post ab. Die Staatsanwaltschaft verschickte beide Verfügungen nochmals per A-Post. Die Nichtanhandnahmeverfügung gelangte X._ am 31. August 2012 zur Kenntnis. Er erhob am 2. September 2012 gegen Ziffer 4 des Dispositivs Beschwerde beim Obergericht des Kantons Bern, auf welche dieses mit Beschluss vom 13. September 2012 nicht eintrat. X._ nahm am 21. September 2012 vom Strafbefehl und obergerichtlichen Nichteintretensentscheid Kenntnis. Er erhob gleichentags durch seinen beigezogenen Verteidiger "vorsorglich" Einsprache gegen den Strafbefehl. C. Am 4. Oktober 2012 stellte er ein Gesuch um Wiederherstellung der Einsprachefrist, das die Staatsanwaltschaft am 11. Oktober 2012 abwies. Die hiergegen erhobene Beschwerde wies das Obergericht am 3. Januar 2013 unter Auferlegung der Verfahrenskosten ab, soweit es darauf eintrat. D. X._ führt Beschwerde in Strafsachen und beantragt, das Urteil des Obergerichts vom 3. Januar 2013 sei aufzuheben, das Gesuch um Wiederherstellung der Rechtsmittelfrist gutzuheissen und diese im Strafbefehl vom 21. August 2012 wiederherzustellen. Eventualiter sei festzustellen, dass die Einsprache rechtzeitig erhoben wurde. Subeventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. E. Die Staatsanwaltschaft verzichtet auf eine Vernehmlassung. Das Obergericht hat sich nicht vernehmen lassen. 