Sachverhalt:
A. Am 16. Januar 2006 erstattete A._ Strafanzeige gegen X._ wegen strafbarer Handlungen gegen Leib und Leben und stellte gleichentags Strafantrag wegen Missbrauchs einer Fernmeldeanlage. Das Untersuchungsrichteramt Schaffhausen stellte am 29. Januar 2007 das Untersuchungsverfahren gegen X._ ein und hielt auf dessen Beschwerde hin am 16. März 2007 zusätzlich fest, dass sich dieser keiner strafbaren Handlung schuldig gemacht habe.
Am 11. Mai 2006 meldete X._ seinerseits beim Friedensrichteramt Schaffhausen Ehrverletzungsklage gegen A._ an. Nach gescheitertem Sühneversuch gelangte er ans Kantonsgericht Schaffhausen, das A._ am 14. August 2007 der üblen Nachrede schuldig sprach und sie zu einer bedingten Geldstrafe von 30 Taessätzen zu Fr. 40.-- bei einer Probezeit von 3 Jahren verurteilte.
B. Gegen das Urteil des Kantonsgerichts Schaffhausen erhob A._ am 3. September 2007 Berufung ans Obergericht des Kantons Schaffhausen. Dieses hob am 20. Mai 2009 den Schuldspruch sowie die Strafsanktion des Kantonsgerichts Schaffhausen auf und sprach sie von Schuld und Strafe frei.
C. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, der angefochtene Entscheid sei aufzuheben, und A._ sei der üblen Nachrede gemäss <ref-law> schuldig zu sprechen.
D. Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. Die Vorinstanz würdigte die Äusserungen der Beschwerdegegnerin, die anlässlich der polizeilichen und untersuchungsrichterlichen Einvernahmen sowie der erstinstanzlichen Hauptverhandlung aussagte, dass sie mehrfach gegen ihren Willen mit dem Beschwerdeführer Geschlechtsverkehr gehabt hätte, als ehrverletzend im Sinne von <ref-law>. Der objektive Tatbestand der üblen Nachrede sei erfüllt (angefochtenes Urteil, S. 14). Die Vorinstanz nahm jedoch an, die Beschwerdegegnerin könne sich auf den Rechtfertigungsgrund der berechtigten Interessen (<ref-law>) sowie auf den Entlastungsbeweis des guten Glaubens (<ref-law>) berufen. Aus diesem Grund hiess sie die Berufung gut.
2. 2.1 Der Beschwerdeführer rügt zunächst eine Verletzung des in <ref-law> gewährleisteten Anspruchs auf rechtliches Gehör. Die erste Instanz habe in ihrem Entscheid einlässlich dargelegt, dass die Voraussetzungen von <ref-law> zur Verweigerung des Entlastungsbeweises nach <ref-law> gegeben seien. Mit diesen Argumenten habe sich die Vorinstanz in keiner Art und Weise auseinandergesetzt (Beschwerde, S. 5).
2.2 Die Vorinstanz führt aus, dass die Beschwerdegegnerin in ihrer Berufungsbegründung zu Recht den Rechtfertigungsgrund der berechtigten Interessen gemäss <ref-law> geltend gemacht habe, da sie vor der Polizei Aussagen über ihre intimen und persönlichen Verhältnisse gemacht und ihre Empfindungen unverfälscht, in guten Treuen und wahrheitsgetreu wiedergegeben habe. Sie habe sowohl vor der Polizei, dem Untersuchungsrichter wie der erstinstanzlichen Verhandlung konsequent dargelegt, weshalb sie sich unterdrückt gefühlt, Angst vor dem Beschwerdeführer gehabt und sich wegen seiner E-Mails und SMS belästigt gefühlt habe (angefochtenes Urteil, S. 14 f.). Es könne somit nicht gesagt werden, dass die Beschwerdegegnerin wider besseres Wissen eine unwahre Behauptung aufgestellt habe. Sie habe sich vielmehr im Rahmen der ihr zustehenden prozessualen Darlegungs- und Begründungspflicht zur Beziehung mit dem Beschwerdeführer geäussert (angefochtenes Urteil, S. 16).
2.3 Die Rüge des Beschwerdeführers ist nicht stichhaltig. Die Vorinstanz setzt sich auf mehreren Seiten mit der Frage auseinander, inwiefern die Beschwerdegegnerin sich auf Rechtfertigungsgründe stützen sowie zum Entlastungsbeweis zugelassen werden könne (angefochtenes Urteil, S. 14 ff.). Die erste Instanz führte zu <ref-law> lediglich aus, dass der Wahrheitsbeweis gemäss <ref-law> ausgeschlossen sei, zumal mit dem Freispruch des Beschwerdeführers rechtskräftig erstellt sei, dass die Vorwürfe nicht der Wahrheit entsprochen hätten. Zudem sei keine begründete Veranlassung für diese Äusserungen ersichtlich (erstinstanzliches Urteil, S. 5). Die Vorinstanz äusserte sich hierzu dahingehend, dass der Freispruch des Beschwerdeführers einzig zu einer Nichtschuldigerklärung geführt habe. Eine Feststellung, dass die Äusserungen der Beschwerdegegnerin nicht der Wahrheit entsprochen hätten, sei dadurch jedoch nicht erfolgt (angefochtenes Urteil, S. 15). Inwiefern die Vorinstanz mit dieser Begründung den Anspruch auf rechtliches Gehör des Beschwerdeführers verletzt haben soll, ist nicht ersichtlich. Die Beschwerde ist in diesem Punkt unbegründet.
3. 3.1 Der Beschwerdeführer wendet sich weiter gegen die Auffassung der Vorinstanz, dass sich die Beschwerdegegnerin auf die Wahrnehmung berechtigter Interessen im Sinne von <ref-law> berufen könne. Die Vorinstanz habe damit Bundesrecht verletzt.
Die Beschwerdegegnerin habe die offensichtlich konfliktreiche Sexualbeziehung wider besseres Wissen in eine Abfolge von Sexualkontakten wider ihren Willen umgedeutet und in der Absicht gehandelt, den Beschwerdeführer beruflich und persönlich zu schädigen. Nach der bundesgerichtlichen Rechtsprechung müssten im Rahmen einer Anzeige die Behauptungen sachbezogen und nicht wider besseres Wissen aufgestellt werden (Beschwerde, S. 6 f.).
3.2 Wer jemanden bei einem anderen eines unehrenhaften Verhaltens oder anderer Tatsachen, die geeignet sind, seinen Ruf zu schädigen, beschuldigt oder verdächtigt, wer eine solche Beschuldigung oder Verdächtigung weiterverbreitet, wird, auf Antrag, wegen übler Nachrede mit Geldstrafe bis zu 180 Tagessätzen bestraft (<ref-law>). Gemäss <ref-law> ist der Beschuldigte nicht strafbar, wenn er beweist, dass die von ihm vorgebrachte oder weiterverbreitete Äusserung der Wahrheit entspricht oder dass er ernsthafte Gründe hatte, sie in guten Treuen für wahr zu halten. Nach Ziff. 3 derselben Bestimmung wird der Beschuldigte zum Beweis nicht zugelassen und ist strafbar für Äusserungen, die ohne Wahrung öffentlicher Interessen oder sonst wie ohne begründete Veranlassung, vorwiegend in der Absicht vorgebracht oder verbreitet werden, jemandem Übles vorzuwerfen, insbesondere, wenn sich die Äusserungen auf das Privat- oder Familienleben beziehen.
3.2 Wer jemanden bei einem anderen eines unehrenhaften Verhaltens oder anderer Tatsachen, die geeignet sind, seinen Ruf zu schädigen, beschuldigt oder verdächtigt, wer eine solche Beschuldigung oder Verdächtigung weiterverbreitet, wird, auf Antrag, wegen übler Nachrede mit Geldstrafe bis zu 180 Tagessätzen bestraft (<ref-law>). Gemäss <ref-law> ist der Beschuldigte nicht strafbar, wenn er beweist, dass die von ihm vorgebrachte oder weiterverbreitete Äusserung der Wahrheit entspricht oder dass er ernsthafte Gründe hatte, sie in guten Treuen für wahr zu halten. Nach Ziff. 3 derselben Bestimmung wird der Beschuldigte zum Beweis nicht zugelassen und ist strafbar für Äusserungen, die ohne Wahrung öffentlicher Interessen oder sonst wie ohne begründete Veranlassung, vorwiegend in der Absicht vorgebracht oder verbreitet werden, jemandem Übles vorzuwerfen, insbesondere, wenn sich die Äusserungen auf das Privat- oder Familienleben beziehen.
3.3 3.3.1 Wie die Vorinstanz zutreffend ausführt (angefochtenes Urteil, S. 14 ff.), kann eine ehrverletzende Äusserung gestützt auf den Rechtfertigungsgrund der Wahrnehmung berechtigter Interessen gemäss <ref-law> zulässig sein. Nach dieser Bestimmung verhält sich rechtmässig, wer handelt, wie es das Gesetz gebietet oder erlaubt, auch wenn die Tat nach dem Strafgesetzbuch oder einem andern Gesetz mit Strafe bedroht ist. Den Rechtfertigungsgrund von <ref-law> können nach der bundesgerichtlichen Rechtsprechung beispielsweise neben Richtern, Beamten oder Anwälten auch die Prozessparteien geltend machen. Letztere können sich bei allfälligen ehrenrührigen Bemerkungen auf ihre prozessualen Darlegungspflichten berufen. Der Zeuge handelt aufgrund seiner Zeugnispflicht rechtmässig, wenn er aussagt, was er für wahr hält. Dies gilt selbst, wenn er bei pflichtgemässer Aufmerksamkeit die Unrichtigkeit seiner vermeintlich wahren Angaben hätte erkennen können (Urteil 6B_68/2009 vom 4. Juni 2009 E. 4 mit Hinweisen). Die Beschwerdegegnerin wurde von der Polizei als Geschädigte und vom Untersuchungsrichter als Zeugin einvernommen (pag. 34 ff. und pag. 85 ff. der Vorakten). Dass die Vorinstanz den Rechtfertigungsgrund von <ref-law> bejaht hat, ist daher nicht zu beanstanden.
3.3.2 Es ist nicht ersichtlich, inwiefern die Vorinstanz die Akten unzutreffend gewürdigt hätte. Der Beschwerdeführer beschränkt sich darauf, der Beschwerdegegnerin vorzuwerfen, sie habe die Aussagen betreffend Sexualkontakte mit ihm wider besseres Wissen gemacht und legt nicht dar, inwiefern dies der Fall gewesen wäre.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substantiiert darlegen, inwiefern die Voraussetzungen gemäss <ref-law> gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre. Er kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substantiiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die den genannten Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3). Die Beschwerde ist daher in diesem Punkt abzuweisen, soweit darauf einzutreten ist.
4. 4.1 Der Beschwerdeführer beanstandet schliesslich die Auffassung der Vorinstanz, dass der Beschwerdegegnerin der Gutglaubensschutz gemäss <ref-law> offenstehe. Die Vorinstanz habe sich mit den Argumenten der ersten Instanz nicht auseinandergesetzt und nicht begründet, weshalb die Beschwerdegegnerin zum Gutglaubensbeweis zugelassen werden soll (Beschwerde, S. 4).
4.2 Wie die Vorinstanz zutreffend ausführt, haben die Rechtfertigungsgründe des Allgemeinen Teils des Strafgesetzbuches, so auch <ref-law>, Vorrang vor dem Entlastungsbeweis im Sinne von <ref-law> (angefochtenes Urteil, S. 16). Dieser kommt nur zum Zug, wenn sich die Straflosigkeit nicht bereits aus einem Rechtfertigungsgrund ergibt (<ref-ruling> E. 1.3.1). Da die Vorinstanz das Vorliegen des Rechtfertigungsgrundes der Wahrnehmung berechtigter Interessen zu Recht bejaht hat, braucht die Frage nicht entschieden zu werden, ob sich die Beschwerdegegnerin mit Erfolg auf den Entlastungsbeweis des guten Glaubens (<ref-law>) berufen kann.
5. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 12. Oktober 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Schneider Keller