Sachverhalt:
A. Am 23. Juni 2009 reichten die Eheleute Z._ bei der Bau- und Werkkommission Lüterkofen-Ichertswil ein Gesuch zum Bau eines neuen Boxenlaufstalls mit Jauchegrube auf Parzelle Nr. 1043 GB Lüterkofen ein. Der geplante Boxenlaufstall hat eine Länge von 32 m und eine Breite von 31 m. Das betroffene Grundstück befindet sich in der Landwirtschaftszone, welche von einer kommunalen Freihaltezone im Sinne von § 36 Abs. 2 des Planungs- und Baugesetzes des Kantons Solothurn vom 3. Dezember 1978 (BGS 711.1; im Folgenden: PBG) überlagert wird. Während der Publikationsfrist erhoben Y._ und die X._ AG Einsprache gegen das Baugesuch. Mit Verfügung vom 14. Mai 2010 erteilte das Bau- und Justizdepartement des Kantons Solothurn seine Zustimmung und wies die Einsprache hinsichtlich der Zonenkonformität ab. Die Bau- und Werkkommission erteilte in der Folge am 18. Mai 2010 die Baubewilligung mit Auflagen.
Gegen die Baubewilligung vom 18. Mai 2010 erhoben Y._ und die X._ AG Beschwerde. Mit Verfügung vom 23. September 2010 wies das Bau- und Justizdepartement die Beschwerden ab. Gegen diesen Entscheid legten Y._ und die X._ AG Beschwerde beim Verwaltungsgericht des Kantons Solothurn ein. Dieses wies die Beschwerden mit Urteil vom 25. Februar 2011 ab, soweit es darauf eintrat.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 1. April 2011 beantragen die X._ AG und Y._ im Wesentlichen, das Urteil des Verwaltungsgerichts sei aufzuheben, die Kosten des Verfahrens vor den Vorinstanzen seien den Beschwerdegegnern aufzuerlegen und den Beschwerdeführern sei für das Verfahren vor den Vorinstanzen eine Parteientschädigung zuzusprechen. Eventuell sei die Angelegenheit zur neuen Beurteilung an das Verwaltungsgericht zurückzuweisen.
Das Verwaltungsgericht des Kantons Solothurn beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Das Bau- und Justizdepartement des Kantons Solothurn schliesst auf Abweisung der Beschwerde. Die privaten Beschwerdegegner wie auch die Bau- und Werkkommission Lüterkofen-Ichertswil haben sich nicht vernehmen lassen. Das ebenfalls zur Vernehmlassung eingeladene Bundesamt für Raumentwicklung hat auf eine Stellungnahme verzichtet.
Mit Präsidialverfügung vom 10. Mai 2011 hat das Bundesgericht das Gesuch der Beschwerdeführer um aufschiebende Wirkung abgewiesen.

Erwägungen:
1. Dem angefochtenen Entscheid liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung zugrunde. Nach Art. 34 Abs. 1 RPG (SR 700) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält keinen Ausschlussgrund (<ref-law>). Angefochten ist ein Entscheid einer letzten kantonalen Instanz, welcher das Verfahren abschliesst (Art. 86 Abs. 1 lit. d, Art. 90 BGG). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen, sind als Eigentümer benachbarter Liegenschaften durch den angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>).
2. 2.1 Die Beschwerdeführer rügen eine Verletzung der Rechtsweggarantie (<ref-law>), von Art. 33 RPG, <ref-law> und von Art. 29 Abs. 1 und 2 BV. Das Verwaltungsgericht, welches im kantonalen Verfahren die einzige richterliche Behörde gewesen sei, habe sich in Verletzung dieser Bestimmungen auf eine Willkürprüfung beschränkt.
2.2 Inwiefern der angefochtene Entscheid Art. 29 Abs. 1 und 2 BV verletzt, legen die Beschwerdeführer nicht dar. Mangels hinreichender Begründung ist auf diese Rügen nicht einzutreten (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG). Näher zu untersuchen ist jedoch, ob die Vorinstanz die Vorgaben von <ref-law>, <ref-law> und Art. 33 RPG beachtet hat.
2.3 Die Rechtsweggarantie (<ref-law>) wird in <ref-law> konkretisiert (Urteil 2C_690/2010 vom 25. Januar 2011 E. 2.1 mit Hinweis). Danach gewährleisten die Kantone, soweit sie nach dem Bundesgerichtsgesetz als letzte kantonale Instanz ein Gericht einzusetzen haben (vgl. <ref-law>), dass diese selbst oder eine vorgängig zuständige andere richterliche Behörde den Sachverhalt frei prüft und das massgebende Recht von Amtes wegen anwendet.
<ref-law> und <ref-law> garantieren bei grundsätzlich allen Rechtsstreitigkeiten Zugang zu wenigstens einem Gericht, das Rechts- und Sachverhaltsfragen umfassend überprüfen kann. Grundsätzlich nicht gefordert ist dagegen eine Kontrolle der Angemessenheit der angefochtenen Entscheide (Urteil 2C_690/2010 vom 25. Januar 2011 E. 2.2 mit Hinweis). Eine Kontrolle der Angemessenheit verlangt indessen Art. 33 Abs. 3 lit. b RPG, wobei diese auch durch eine nichtrichterliche Beschwerdebehörde gewährleistet werden kann. Im vorliegenden Fall, wo das Verwaltungsgericht nicht als einzige kantonale Beschwerdebehörde amtete, ergab sich für dieses deshalb aus Art. 33 Abs. 3 lit. b RPG keine weiterreichende Prüfungspflicht als aus <ref-law> und <ref-law>.
Sowohl nach <ref-law> als auch nach <ref-law> und Art. 33 Abs. 3 lit. b RPG müssen die Gerichte den Handlungsspielraum, welcher das Gesetz der Verwaltung einräumt, respektieren (zur Publikation vorgesehenes Urteil 1D_1/2011 vom 13. April 2011 E. 2.5 mit Hinweisen; Urteil 1C_310/2009 vom 17. März 2010 E. 2.2.2 mit Hinweisen; HEINZ AEMISEGGER/STEPHAN HAAG, Praxiskommentar zum Rechtsschutz in der Raumplanung, 2010, N. 77 zu Art. 34 RPG). Dies gilt insbesondere im Bereich der Gemeindeautonomie (<ref-law>). Indessen darf das zum Rechtsschutz im Sinne von <ref-law>, <ref-law> und Art. 33 Abs. 3 lit. b RPG berufene Gericht seine Kognition nicht auf Willkür beschränken (zur Publikation vorgesehenes Urteil 1D_1/2011 vom 13. April 2011 E. 2.5.1-2.5.3; <ref-ruling> E. 2d S. 8; je mit Hinweisen; AEMISEGGER/HAAG, a.a.O., N. 77 zu Art. 33 RPG).
2.4 Das Verwaltungsgericht führte aus, § 36 Abs. 2 PBG lasse den Gemeinden offen, ob sie weitere Freihaltegebiete ausscheiden und wie sie diese gestalten und regeln wollten. Die Gemeinden seien in diesem Bereich autonom.
Aus den weiteren Erwägungen im angefochtenen Entscheid ist nicht klar ersichtlich, welchen Prüfungsmassstab das Verwaltungsgericht anlegte. Die betreffenden Ausführungen sind teils widersprüchlich. So wird dargelegt, dass die Auslegung von § 12 Abs. 2 des Zonenreglements der Gemeinde Lüterkofen-Ichertswil (im Folgenden: ZR) durch die Gemeinde vertretbar und auf jeden Fall nicht willkürlich sei. Auf ein Gegenargument der Beschwerdeführer erwiderte das Verwaltungsgericht, die Beschwerdeführer befänden sich "mit ihrer Argumentation bereits im Bereich der Auslegung von § 12 Abs. 2 ZR". Abschliessend hielt es fest: "Da die Gemeinde Lüterkofen-Ichertswil im vorliegenden Fall sowohl Gesetzgeberin als auch Rechtsanwenderin des betreffenden Zonenreglements mit dessen Freihaltezone ist, hat sie auch das Recht, dieses selber auszulegen. Weil die vorliegende Auslegung im Bereich der Gemeindeautonomie liegt, wird sie durch das Verwaltungsgericht nur auf Willkür überprüft. Da die Auslegung vertretbar und nicht willkürlich ist, erachtet sie das Verwaltungsgericht als massgebend".
Das Verwaltungsgericht hat somit einerseits seine Kognition ausdrücklich auf Willkür beschränkt, die Auslegung durch die Gemeinde aber trotzdem als vertretbar (und nicht bloss als nicht willkürlich) bezeichnet. In Bezug auf das erwähnte Gegenargument schliesslich wies es die Beschwerdeführer darauf hin, sie würden sich mit ihrer Argumentation bereits "im Bereich der Auslegung von § 12 Abs. 2 ZR" bewegen. Dieser Hinweis ergibt nur vor dem Hintergrund einer Willkürkognition Sinn. Gleich im Anschluss an diesen Hinweis erwog das Verwaltungsgericht indessen erneut, die Gemeinde habe sich "auf vertretbare Weise" entschieden, § 12 Abs. 2 ZR anders auszulegen. Ob angesichts dieser widersprüchlichen Erwägungen gesagt werden kann, das Verwaltungsgericht habe sich im Ergebnis in unzulässiger Weise auf eine Willkürprüfung beschränkt, kann indessen offen bleiben. Wie sich aus den nachfolgenden Erwägungen ergibt, ist der angefochtene Entscheid ohnehin aufzuheben.
3. 3.1 Die Beschwerdeführer rügen eine willkürliche Auslegung von § 12 ZR. Diese Bestimmung regelt die Freihaltezone und hat folgenden Wortlaut:
1 Zweck
Die Freihaltezone dient der Freihaltung der mehrheitlich unüberbauten Gebiete angrenzend an den Dorfkern von Lüterkofen und der Vorranggebiete Natur und Landschaft von Hochbauten. Sie ist der Landwirtschaftszone überlagert.
2 Bauten und Anlagen
Das Erstellen von Hochbauten sowie landschaftsverändernde Terrainveränderungen und Deponien sind untersagt. Der Bestand der bestehenden Bauten sowie die Erweiterung zu landwirtschaftlichen Zwecken bleiben gewährleistet. Die Baubehörde kann ausnahmsweise kleinere Nebenbauten bewilligen.
3.2 Die Vorinstanz legte dar, § 12 Abs. 2 ZR lasse verschiedene Interpretationsmöglichkeiten zu. Gemäss der Bau- und Werkkommission solle die Erweiterung zu landwirtschaftlichen Zwecken vom Verbot des Erstellens von Hochbauten für bestehende Betriebe ausgenommen werden. Absatz 2 Satz 3, welcher ausnahmsweise die Bewilligung von kleineren Nebenbauten erlaube, beziehe sich nur auf nichtlandwirtschaftliche Betriebe. Die Gemeinde wolle in der Freihaltezone Neuansiedlungen von Landwirtschaftsbetrieben ausschliessen, jedoch den bestehenden Betrieben deren Erweiterung gewährleisten. Denn gerade die bestehenden Betreibe ermöglichten durch ihre Aufrechterhaltung der Bewirtschaftung die vorliegende Siedlungsstruktur, welche die Freihaltezone schützen wolle. Für die Auslegung der Gemeinde spreche ferner der Umstand, dass die heutigen landwirtschaftlichen Betriebe zunehmendem wirtschaftlichem Druck ausgesetzt seien, welcher sie zwinge, ihre Hofgrösse massiv zu erhöhen. Was die Beschwerdeführer dagegen vorbringen würden, überzeuge nicht. So ergebe sich aus dem Wortlaut von § 12 Abs. 2 ZR nicht, dass sich das Wort "Erweiterung" nur auf bestehende Bauten beziehe. Dem Begriff der Erweiterung könne durchaus auch selbstständige Bedeutung zukommen. Auch das Argument, die Auslegung durch die Gemeinde ergebe gar keinen Sinn, weil nichtlandwirtschaftliche Bauten grundsätzlich bereits durch die Landwirtschaftszone ausgeschlossen seien, schlage fehl. Nichtlandwirtschaftliche Bauten wären nämlich ohne Freihaltezone aufgrund einer Ausnahmebewilligung gemäss Art. 24 ff. RPG zulässig.
3.3 Die Beschwerdeführer bringen vor, der klare Wortlaut der Bestimmung spreche gegen die Auslegung des Verwaltungsgerichts. Auch §§ 10 und 11 ZR zur Ortsbildschutzzone und zur kommunalen Uferschutzzone würden sich nur auf Bauten und Anlagen, nicht aber auf ganze Betriebe beziehen. Schliesslich lasse das Verwaltungsgericht im Hinblick auf Sinn und Zweck von § 12 Abs. 2 ZR das Leitbild der Gemeinde vom 8. Juni 1994 ("Die räumliche Entwicklung von Lüterkofen-Ichertswil: Ein Leitbild für unsere Gemeinde") und den nachfolgenden Vorprüfungsbericht des kantonalen Amts für Raumplanung vom 22. Dezember 1995 ("Lüterkofen-Ichertswil betreffend: Ortsplanungsrevision Teil Siedlung/Vorprüfung") ausser Acht. Danach werde deutlich, dass die kommunale Freihaltezone gemäss § 12 ZR klar die bisher bestehende natürliche Zäsur zwischen Dorfkern und Neubauquartieren bewahren solle. Durch Neubauten, vor allem solche in den vorliegend geplanten Dimensionen, würde diese natürliche Zäsur beeinträchtigt.
3.4 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 S. 5 mit Hinweisen).
3.4 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 S. 5 mit Hinweisen).
3.5 3.5.1 Ausgangspunkt jeder Auslegung bildet der Wortlaut der Bestimmung. Ist der Text nicht ganz klar und sind verschiedene Interpretationen möglich, so muss nach der wahren Tragweite der Bestimmung gesucht werden, wobei alle Auslegungselemente zu berücksichtigen sind (Methodenpluralismus). Dabei kommt es namentlich auf den Zweck der Regelung, die dem Text zugrunde liegenden Wertungen sowie auf den Sinnzusammenhang an, in dem die Norm steht. Die Gesetzesmaterialien sind zwar nicht unmittelbar entscheidend, dienen aber als Hilfsmittel, den Sinn der Norm zu erkennen. Vom Wortlaut darf abgewichen werden, wenn triftige Gründe für die Annahme bestehen, dass dieser nicht den wahren Sinn der Regelung wiedergibt. Solche Gründe können sich aus der Entstehungsgeschichte, aus Sinn und Zweck der Norm oder aus ihrem Zusammenhang mit anderen Gesetzesbestimmungen ergeben. Sind mehrere Auslegungen möglich, ist jene zu wählen, die den verfassungsrechtlichen Vorgaben am besten entspricht. Eine verfassungskonforme Auslegung findet dabei im klaren Wortlaut und Sinn einer Gesetzesbestimmung ihre Schranken (<ref-ruling> E. 3 S. 154; <ref-ruling> E. 2.3 S. 376; zur Publikation vorgesehenes Urteil 4A_578/2010 vom 11. April 2011 E. 2.4.1; je mit Hinweisen).
3.5.2 Nach dem Wortlaut von § 12 Abs. 2 Satz 2 ZR ("Der Bestand der bestehenden Bauten sowie die Erweiterung zu landwirtschaftlichen Zwecken bleiben gewährleistet") bezieht sich der Begriff der Erweiterung auf die bestehenden Bauten, auch wenn dies noch klarer zum Ausdruck gebracht würde, wenn es "deren Erweiterung" hiesse. Der Auffassung der Vorinstanz, dass dem Begriff der Erweiterung durchaus selbstständige Bedeutung zukommen könne, ist entgegenzuhalten, dass der Begriff, für sich genommen, nichts besagt. Die entscheidende Frage ist, was erweitert werden darf. Dafür, dass Betriebe erweitert werden dürfen - in dem Sinne, dass neue Hochbauten zu den bestehenden Bauten hinzu erstellt werden dürfen -, enthält der Wortlaut keinerlei Anhaltspunkte.
Eine zusammenhängende Lektüre von Satz 2 und Satz 3 bestätigt dieses Ergebnis. Dass die Baubehörde gemäss Satz 3 ausnahmsweise kleinere Nebenbauten bewilligen kann, erscheint ausschliesslich unter der Prämisse als sinnvoll, dass Nebenbauten nicht schon nach Satz 2 zulässig sind. Die Vorinstanz macht diesbezüglich zwar geltend, die ausnahmsweise Bewilligung kleinerer Nebenbauten beziehe sich nur auf nichtlandwirtschaftliche Betriebe. Nichtlandwirtschaftliche Betriebe, also Bauten und Anlagen, die den Nutzungsvorschriften der Landwirtschaftszone nicht entsprechen, sind jedoch nur unter den Voraussetzungen von Art. 24 ff. RPG zulässig. Es liegt bedeutend näher, den Begriff "ausnahmsweise" als Hinweis auf das Ermessen der Baubehörde zu verstehen als auf die verbindlichen Vorgaben des Bundesrechts in Art. 24 ff. RPG. Zumindest gibt es für diese zweite, von der Vorinstanz vertretene Variante im Wortlaut wiederum keine Anhaltspunkte.
In Bezug auf den Normzweck schliesslich ist keine eindeutige Aussage möglich. § 12 ZR versucht augenscheinlich einen Ausgleich zu finden zwischen einer (bewahrenden) Freihaltung des in Absatz 1 umschriebenen mehrheitlich unüberbauten Gebiets und der möglichen Erweiterung der bestehenden Landwirtschaftsbetriebe. Ein eigentlicher Vorrang des einen oder anderen Zwecks ist nicht ersichtlich. Die Vorinstanz hat diesbezüglich die Auffassung der Bau- und Werkkommission zum Gesetzeszweck erklärt und ist gestützt darauf vom Vorrang der Erweiterung bestehender Landwirtschaftsbetriebe ausgegangen. Damit hat sie die Bestimmung indessen nicht aus sich heraus ausgelegt, sondern ist von einem Gesetzeszweck ausgegangen, der so im Gesetzestext nicht zum Ausdruck kommt (vgl. <ref-ruling> E. 1.6 S. 39). Zwar argumentierte die Vorinstanz hilfsweise auch, dass gerade die bestehenden Betriebe durch ihre Aufrechterhaltung der Bewirtschaftung die vorliegende Siedlungsstruktur ermöglichten, welche die Freihaltezone schützen solle. Diese Darstellung ist jedoch insofern nicht überzeugend, als kaum verständlich ist, weshalb die Freihaltezone ihren Zweck nur dann auf Dauer erfüllen können soll, wenn zusätzliche Hochbauten bewilligt werden.
3.5.3 Eine grammatikalische und systematische Auslegung von § 12 Abs. 2 ZR führt somit zum klaren Ergebnis, dass sich der Begriff der Erweiterung auf die im vorangehenden Satzteil genannten bestehenden Bauten bezieht und nicht auf den ganzen landwirtschaftlichen Betrieb. Dieses Ergebnis wird nach dem Gesagten auch nicht durch eine Auslegung nach dem Normzweck in Frage gestellt. Die gegenteilige Auslegung durch die Bau- und Werkkommission, welche das Verwaltungsgericht gestützt hat, erscheint als nicht haltbar. Die Rüge der Verletzung des Willkürverbots ist begründet.
4. Die Beschwerde ist gutzuheissen, soweit darauf einzutreten ist, und der angefochtene Entscheid aufzuheben. Eine Beurteilung der weiteren von den Beschwerdeführern vorgetragenen Rügen erübrigt sich. Es obliegt dem Verwaltungsgericht, die Kosten- und Entschädigungsfolgen für das vorangegangene Verfahren neu zu regeln, weshalb die Angelegenheit diesbezüglich an die Vorinstanz zurückzuweisen ist (<ref-law>).
Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdegegnern aufzuerlegen (<ref-law>). Die Beschwerdegegner haben den obsiegenden, anwaltlich vertretenen Beschwerdeführern eine angemessene Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, und das Urteil vom 25. Februar 2011 des Verwaltungsgerichts des Kantons Solothurn sowie die Baubewilligung der Bau- und Werkkommission Lüterkofen-Ichertswil vom 18. Mai 2010 werden aufgehoben.
Die Angelegenheit wird zur neuen Beurteilung der Kosten- und Entschädigungsfolgen an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdegegnern auferlegt.
3. Die Beschwerdegegner haben die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Bau- und Werkkommission Lüterkofen-Ichertswil, dem Bau- und Justizdepartement und dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 15. Juli 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Fonjallaz Dold