Sachverhalt: A. Das Kantonsgericht Appenzell Ausserrhoden verurteilte X._ am 28. August 2006 insbesondere wegen vorsätzlicher Tötung zu 9 Jahren Zuchthaus und widerrief den bedingten Vollzug für eine Vorstrafe von 5 Tagen Gefängnis. Es erachtete es als erwiesen, dass X._ am 28. Februar 2005 jemanden erschossen hatte. Auf Appellation von X._ und Anschlussappellation der Staatsanwaltschaft hin bestätigte das Obergericht des Kantons Appenzell Ausserrhoden am 10. Juli 2007 das kantonsgerichtliche Urteil im Schuldpunkt, passte die Strafe an das neue Recht an, erhöhte diese um ein Jahr auf 10 Jahre Freiheitsstrafe und verhängte zusätzlich eine Busse von 400 Franken. Die von X._ dagegen erhobene Beschwerde in Strafsachen hiess das Bundesgericht am 14. Juli 2008 gut. Es hob den Entscheid des Obergerichts auf und wies die Sache an dieses zurück (Urteil 6B_219/2008). Das Bundesgericht befand, das Obergericht habe sich in willkürlicher Weise über seine in Art. 21 des Gesetzes vom 30. April 1978 des Kantons Appenzell Ausserrhoden über den Strafprozess (Strafprozessordnung, StPO; bGS 321.1) festgelegte Pflicht zur Erforschung der materiellen Wahrheit hinweggesetzt. Die kantonalen Behörden hätten einen Mann, der sich bei der Polizei gemeldet und das Tatgeschehen verfolgt habe, als Zeugen einvernehmen müssen (E. 2.5 f.). Mit Beschluss vom 22. September 2008 wies das Obergericht die Akten zur Durchführung eines korrekten Verfahrens und Neubeurteilung im Sinne der Erwägungen an die Staatsanwaltschaft zurück. B. Am 9. März 2009 verlangte X._ den Ausstand von Staatsanwalt Christian Bötschi wegen Befangenheit. X._ stützte dieses Begehren auf einen Artikel in der Online-Ausgabe des "St. Galler Tagblatt" vom 14. Februar 2009. Dieser trägt die Überschrift "Neue Untersuchungen in Tötungsfall" und enthält folgende Passage: "Staatsanwalt Christian Bötschi sagt, das Urteil liege im Ermessensspielraum der Richter, aber an den Ergebnissen des Beweisverfahrens und am Tathergang werde der Zeuge nichts ändern." Mit Stellungnahme vom 11. März 2009 beantragte Staatsanwalt Bötschi die Ablehnung des Ausstandsbegehrens. Am 13. März 2009 wies das Departement Sicherheit und Justiz des Kantons Appenzell Ausserrhoden (im Folgenden: Departement) das Ausstandsbegehren ab. C. X._ führt Beschwerde in Strafsachen mit dem Antrag, der Entscheid des Departements sei aufzuheben und Staatsanwalt Bötschi als befangen zu erklären. D. Das Departement und Staatsanwalt Bötschi haben Vernehmlassungen eingereicht je mit dem Antrag, die Beschwerde abzuweisen. X._ hat dazu Stellung genommen. Er hält an seinen Anträgen fest. E. Mit Verfügung vom 8. April 2009 hat der Präsident der I. öffentlich-rechtlichen Abteilung das Gesuch um Erlass einer vorsorglichen Massnahme abgewiesen. 