Sachverhalt: A. Die Jugendanwaltschaft Appenzell Ausserrhoden sprach X._ am 6. Januar 2009 wegen sexueller Handlungen mit Kindern schuldig. Sie bestrafte ihn mit einer Freiheitsstrafe von einem Tag und einer Busse von Fr. 200.--. Mit Verfügung gleichen Datums stellte sie das Verfahren wegen Vergewaltigung, sexueller Nötigung sowie Strassenverkehrsdelikten ein. Auf das von X._ erhobene Rechtsmittel änderte sie am 2. März 2009 die Begründung der Strafverfügung. Auf erneutes Rechtsmittel hin ging sie zwar von einem strafbaren Verhalten betreffend sexuelle Handlungen mit Kindern aus, stellte aber das Verfahren in Anwendung des Opportunitätsprinzips am 15. Mai 2009 ein. Sie sprach X._ eine Parteientschädigung von Fr. 8'989.60 sowie eine Haftentschädigung von Fr. 300.-- zu und verpflichtete ihn, Fr. 300.-- an die Untersuchungskosten zu bezahlen. Seinen Rekurs gegen die Einstellungsverfügung vom 15. Mai 2009 wies die Staatsanwaltschaft Appenzell Ausserrhoden am 30. Juni 2009 ab. B. Dagegen erhebt X._ Beschwerde in Strafsachen. Er beantragt, der Rekursentscheid sei aufzuheben. Es sei festzustellen, dass er sich nicht der sexuellen Handlungen mit Kindern strafbar gemacht habe und ihm zu Unrecht Untersuchungskosten auferlegt worden seien. Er sei für die seit dem 16. Dezember 2008 aufgelaufenen Parteikosten mit Fr. 4'062.50 zuzüglich Mehrwertsteuer zu entschädigen. Eventualiter sei die Sache zur neuen Entscheidung an die Staatsanwaltschaft zurückzuweisen. C. Die Staatsanwaltschaft des Kantons Appenzell Ausserrhoden beantragt in ihrer Vernehmlassung vom 11. Januar 2010 die Abweisung der Beschwerde. Die Jugendanwaltschaft verzichtet mit Eingabe vom 13. Januar 2010 auf eine Vernehmlassung.