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.

Erwägungen:
1. 1.1 Der angefochtene Entscheid betrifft ein Strafverfahren und stützt sich auf kantonales Strafprozessrecht. Damit ist gemäss Art. 78 Abs. 1 BGG die Beschwerde in Strafsachen gegeben.
1.2 Gemäss Art. 17 Abs. 1 Ziff. 1 i.V.m. Art. 9 und Art. 203 StPO steht kein kantonales Rechtsmittel zur Verfügung. Die Beschwerde ist daher nach Art. 80 i.V.m. Art. 130 Abs. 1 BGG zulässig.
1.3 Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen und ist als Beschuldigter gemäss Art. 81 Abs. 1 lit. a und b Ziff. 1 BGG zur Beschwerde befugt.
1.4 Beim angefochtenen Entscheid handelt es sich um einen nach Art. 92 BGG anfechtbaren Zwischenentscheid.
2. 2.1 Der Beschwerdeführer rügt (Beschwerde S. 4 ff.), die Vorinstanz habe die Bestimmungen der Strafprozessordnung über den Ausstand willkürlich angewandt und damit gegen Art. 9 BV verstossen. Überdies habe sie seinen Anspruch auf unparteiische und unvoreingenommene Behandlung nach Art. 29 Abs. 1 und Art. 30 Abs. 1 BV sowie Art. 6 Ziff. 1 EMRK verletzt.
2.2 Gemäss Art. 15 Ziff. 3 StPO kann jeder Beamte oder Richter von einem Verfahrensbeteiligten abgelehnt werden, wenn er infolge besonderer Tatsachen als befangen erscheint.
Nach der in Art. 30 Abs. 1 BV und Art. 6 Ziff. 1 EMRK enthaltenen Garantie des verfassungsmässigen Richters hat der Einzelne Anspruch darauf, dass seine Sache von einem unparteiischen, unvoreingenommenen und unbefangenen Richter ohne Einwirken sachfremder Umstände entschieden wird. Liegen bei objektiver Betrachtungsweise Gegebenheiten vor, die den Anschein der Befangenheit und die Gefahr der Voreingenommenheit zu begründen vermögen, so ist die Garantie verletzt (<ref-ruling> E. 2.1, mit Hinweisen).
Staatsanwalt Bötschi ist hier unstreitig nicht in richterlicher Funktion, sondern als Ankläger tätig. Die Ausstandspflicht beurteilt sich daher nach der Rechtsprechung gemäss Art. 29 Abs. 1 BV (<ref-ruling> E. 2b S. 198).
Der Gehalt von Art. 30 Abs. 1 BV darf nicht unbesehen auf nicht richterliche Behörden bzw. auf Art. 29 Abs. 1 BV übertragen werden (<ref-ruling> E. 2b S. 198). Auch nach Art. 29 Abs. 1 BV gelten für einen Staatsanwalt gewisse Mindestanforderungen an die Unabhängigkeit, die allerdings nicht so weit reichen wie die Garantien nach Art. 30 Abs. 1 BV. Bei einem Staatsanwalt bildet der Umstand, dass er im Prozess einen demjenigen des Angeklagten entgegengesetzen Standpunkt einnimmt und die Beweismittel anders würdigt, keinen Grund, der den Schluss auf Befangenheit zuliesse (<ref-ruling> E. 2d S. 147 f.). Der Staatsanwalt ist zwar zu einer sachlichen und objektiven Amtsführung verpflichtet. Er nimmt jedoch als Partei am Verfahren teil. Er kann und muss damit seinen Parteistandpunkt als Ankläger vertreten. Dementsprechend ist er in seinen Äusserungen gegenüber der Presse freier als ein Richter oder ein Untersuchungsrichter (jedenfalls vor Abschluss der Untersuchung), die zu strikter Unparteilichkeit verpflichtet sind (Urteil 1P.528/2002 vom 3. Februar 2003 E. 4.2).
2.3 Staatsanwalt Bötschi bringt vor, der Journalist habe seine Äusserungen ungenau und verkürzt wiedergegeben (Vernehmlassung S. 3; Stellungnahme vom 11. März 2009 S. 1). Er - Staatsanwalt Bötschi - habe gesagt, die bisher erhobenen Beweise (Erkenntnisse des Instituts für Rechtsmedizin etc.) behielten ihre Beweiskraft und entfielen unabhängig von dem, was der Zeuge aussagen werde, nicht.
Im fraglichen Zeitungsartikel schreibt der Journalist, was Staatsanwalt Bötschi gesagt habe. Es geht somit um eine mündliche Auskunft. Bei einer solchen kann es leicht vorkommen, dass sie der Journalist nicht wörtlich und deshalb ungenau oder verkürzt wiedergibt. Es erübrigt sich jedoch, ein Beweisverfahren (Art. 55 f. BGG) darüber durchzuführen, was Staatsanwalt Bötschi genau gesagt hat. Selbst wenn er sich wörtlich so ausgedrückt haben sollte, wie es im Zeitungsartikel steht, wäre aus den folgenden Erwägungen kein Ausstandsgrund gegeben.
2.4 Gemäss Art. 7 Abs. 2 StPO führt das Verhöramt die Strafuntersuchung, also nicht der Staatsanwalt. Dieser ist nach Art. 8 Abs. 3 StPO öffentlicher Ankläger und hat damit Parteistellung. Dem ist nach der dargelegten Rechtsprechung bei der Beurteilung der Ausstandsfrage Rechnung zu tragen.
Als öffentlicher Ankläger durfte und musste sich Staatsanwalt Bötschi Gedanken darüber machen, wie die Beweise aus seiner Sicht zu würdigen seien. Nach dem Zeitungsartikel sagte er, an den Ergebnissen des Beweisverfahrens und am Tathergang werde der Zeuge - der einen Tag nach der Tat polizeilich befragt worden war - nichts ändern. Darin liegt eine antizipierte Beweiswürdigung. Diese stellt keinen Ausstandsgrund dar. Wie dargelegt, ist nach der Rechtsprechung nicht auf Befangenheit zu schliessen, wenn der Staatsanwalt einen vom Angeklagten abweichenden Standpunkt einnimmt und die Beweise anders würdigt als dieser. Nach dem Zeitungsartikel äusserte Staatsanwalt Bötschi im Übrigen seine persönliche Erwartung vor der Zeugeneinvernahme. Dass er auch dann nicht gewillt wäre, auf seine Position zurückzukommen, falls sich aufgrund der Zeugeneinvernahme neue, unvorhergesehene Gesichtspunkte ergäben, sagte Staatsanwalt Bötschi nicht.
Wesentlich ist sodann Folgendes: Wie sich aus dem Urteil des Bundesgerichts vom 14. Juli 2008 ergibt (S. 5 f. E. 2.6), belastete der Augenzeuge bei der polizeilichen Befragung den Beschwerdeführer stärker, als das Obergericht in der Folge annahm. Staatsanwalt Bötschi legte in der Vernehmlassung des damaligen bundesgerichtlichen Verfahrens denn auch dar, der Augenzeuge belaste den Beschwerdeführer schwer. Ging somit Staatsanwalt Bötschi (nachvollziehbar) davon aus, beim Augenzeugen handle es sich um einen Belastungszeugen, wirkte es sich zugunsten des Beschwerdeführers aus, wenn Staatsanwalt Bötschi gesagt haben sollte, die Einvernahme des Augenzeugen werde am Beweisergebnis nichts ändern. Damit hätte Staatsanwalt Bötschi zum Ausdruck gebracht, dass es nach seiner Auffassung bei der für den Beschwerdeführer günstigeren obergerichtlichen Sachverhaltsannahme bleiben und der Beschwerdeführer nicht schwerer belastet werde. Ging demnach die im Zeitungsartikel wiedergegebene Aussage von Staatsanwalt Bötschi gar nicht zulasten des Beschwerdeführers, hatte die Vorinstanz erst recht keinen Anlass, dessen Ausstandsbegehren stattzugeben. Die Vorinstanz legt das (angefochtener Entscheid S. 3 E. 2.c) zutreffend dar.
3. Die Beschwerde ist danach abzuweisen.
Da sie aussichtslos war, kann die unentgeltliche Rechtspflege und Verbeiständung gemäss Art. 64 BGG nicht bewilligt werden.
Der Beschwerdeführer befindet sich seit über vier Jahren in Untersuchungshaft bzw. im vorzeitigen Strafvollzug. Von seiner Bedürftigkeit ist deshalb auszugehen. Mit Blick darauf wird auf die Erhebung von Kosten verzichtet (Art. 66 Abs. 1 Satz 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Es werden keine Kosten erhoben.
4. Dieses Urteil wird dem Beschwerdeführer, Staatsanwalt Bötschi, dem Verhöramt des Kantons Appenzell Ausserrhoden und dem Departement Sicherheit und Justiz des Kantons Appenzell Ausserrhoden schriftlich mitgeteilt.
Lausanne, 30. Juni 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Härri