Sachverhalt: A. Am 14. Januar 2009 erhob A.X._ Strafklage gegen seine von ihm getrennt lebende Ehefrau B.X._ wegen Verdachts der Veruntreuung und Falschbeurkundung. Am 21. Januar 2009 ergänzte er die Strafklage, nachdem ihm die Staatsanwaltschaft des Kantons St. Gallen am 19. Januar 2009 diesbezüglich verschiedene Fragen gestellt hatte. Mit Verfügung vom 26. Januar 2009 trat das Untersuchungsamt St. Gallen auf die Strafklage von A.X._ wegen Verspätung des Strafantrags betreffend Veruntreuung sowie offenkundiger Ermangelung der objektiven und subjektiven Tatbestandsmässigkeit der Urkundenfälschung/Falschbeurkundung nicht ein. B. Gegen diese Nichteintretensverfügung erhob A.X._ am 10. Februar 2009 Beschwerde an die Anklagekammer des Kantons St. Gallen. Am 29. April 2009 wies diese die Beschwerde ab. C. A.X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, der angefochtene Entscheid sei aufzuheben und die Staatsanwaltschaft des Kantons St. Gallen anzuweisen, gegen B.X._ eine Strafuntersuchung wegen Veruntreuung, Urkundenfälschung sowie allfälliger weiterer Tatbestände zu eröffnen. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. D. Die Staatsanwaltschaft des Kantons St. Gallen sowie B.X._ beantragen die Abweisung der Beschwerde. Die Anklagekammer des Kantons St. Gallen hat auf eine Vernehmlassung verzichtet. A.X._ hat eine Stellungnahme eingereicht und seine in der Beschwerde vorgebrachte Argumentation unterstrichen.