Sachverhalt: A. Die Eheleute X._ reichten bei der Bauverwaltung Selzach nachträglich ein Gesuch für eine Einzäunung auf ihrem Grundstück ein. Der Zaun liegt grösstenteils in der Landwirtschaftszone, welche vom Juraschutz überlagert ist. Er besteht aus 1,4 m hohen Holzpfosten mit Bändern und dient der Pferdehaltung. Mit Verfügung vom 15. Oktober 2008 verweigerte das Bau- und Justizdepartement des Kantons Solothurn die erforderliche Zustimmung und setzte Frist zur Beseitigung der Einfriedung. Es begründete seinen Entscheid damit, dass Bauten und Anlagen, die der Freizeitlandwirtschaft dienen, nicht zonenkonform seien. Eine hobbymässige Pferdehaltung sei nicht auf einen Standort ausserhalb der Bauzone angewiesen. Gegen die Verfügung des Bau- und Justizdepartements gelangten die Eheleute X._ ans Verwaltungsgericht des Kantons Solothurn. Dieses hiess die Beschwerde mit Urteil vom 13. Februar 2009 gut, hob die Verfügung auf und wies die Sache zu neuem Entscheid zur Bewilligung an die Vorinstanz zurück. Zur Begründung führte das Verwaltungsgericht Folgendes aus: Die Pflicht zur Einholung einer Baubewilligung nach Art. 22 des Bundesgesetzes vom 22. Juni 1979 über die Raumplanung (Raumplanungsgesetz, RPG; SR 700) sei sowohl für die Umnutzung von Wiesland in eine ständige Pferdeweide als auch für deren Einzäunung zu bejahen. Unbestritten sei, dass im vorliegenden Fall eine Hobbytierhaltung zur Beurteilung anstehe. Freizeit- und Hobbylandwirtschaft seien gemäss Art. 34 Abs. 5 der Raumplanungsverordnung vom 28. Juni 2000 (RPV; SR 700.1) in der Landwirtschaftszone nicht zonenkonform, weshalb eine ordentliche Baubewilligung nach Art. 22 RPG nicht in Betracht komme, sondern die Voraussetzungen zur Erteilung einer Ausnahmebewilligung zu prüfen seien. Nach der Rechtsprechung sei die Voraussetzung der Standortgebundenheit von Ställen, Reithallen und dergleichen für die hobby- oder gewerbsmässige Pferdehaltung durch Nichtlandwirte zu verneinen. Die Erteilung einer Ausnahmebewilligung könne daher nicht auf die Bestimmung von Art. 24 RPG abgestützt werden. Diese könne aber gestützt auf Art. 24d Abs. 1bis RPG erteilt werden. Hinzu komme, dass das Volkswirtschaftsdepartement des Kantons Solothurn den Kauf des Landes als Pferdeweide bewilligt habe. Das Departement habe die Eheleute X._ nicht darauf aufmerksam gemacht, dass noch eine Baubewilligung erforderlich sei, um das Land bestimmungsgemäss zu nutzen. Sie könnten sich somit auch auf den Vertrauensschutz berufen. B. Der Kanton Solothurn hat gegen das Urteil des Verwaltungsgerichts beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten ergriffen. Neben der Aufhebung des angefochtenen Urteils beantragt er, es sei festzustellen, dass nach Art. 24d Abs. 1bis RPG für die Pferdeeinzäunung keine (nachträgliche) Baubewilligung erteilt werden darf. C. Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Die Eheleute X._ schliessen ebenfalls auf Beschwerdeabweisung und beantragen, es sei festzustellen, dass in casu keine Ausnahmebewilligung nach Art. 24 RPG erforderlich sei. Die Einwohnergemeinde Selzach liess sich vernehmen, ohne ausdrücklich einen Antrag zu stellen. Das Bundesamt für Raumentwicklung (ARE) als beschwerdeberechtigte Bundesverwaltungsbehörde beantragt Gutheissung der Beschwerde. Der Kanton Solothurn liess sich nochmals vernehmen. 