Faits:
A. A._ et B._ sont propriétaires de la parcelle n° 2369 du registre foncier de la commune de Travers (devenue commune de Val-de-Travers à la suite d'une fusion de communes le 1er janvier 2009) au lieu-dit les "Petites Lacherelles". En octobre 1991, ils ont obtenu l'autorisation de reconstruire sur cette parcelle, sise hors de la zone à bâtir, une ferme incendiée quelques années auparavant. Les plans mis à l'enquête mentionnaient un rural et un réduit. Le 2 mars 2005, ayant constaté qu'un atelier de serrurerie était installé dans la ferme en question, le Département de la gestion du territoire du canton de Neuchâtel (ci-après: le département) a imparti un délai à A._ pour demander un changement d'affectation de cet immeuble.
A._ exploite par ailleurs une entreprise de serrurerie à Travers. Il a obtenu en 1998 l'autorisation d'implanter, à titre provisoire, un hangar sur la parcelle n° 2079. Le 26 mai 2000, le Conseil communal de Travers lui a ordonné de remettre les lieux en état avec un délai échéant au 31 juillet 2000. A._ a recouru contre cette décision auprès du département. Par décision du 23 février 2005, le département a accordé la dérogation nécessaire à la création d'un hangar sur la parcelle n° 2079 "à condition que A._ s'engage à y regrouper la majeure partie de son activité actuellement située aux Petites Lacherelles".
B. Le 15 avril 2005, A._ et B._ ont déposé une demande de mise en conformité de l'atelier de serrurerie installé aux "Petites Lacherelles" sur la parcelle n° 2369. Durant la mise à l'enquête publique, les membres de l'hoirie X._ ainsi que D._ et C._, ont formé opposition. Par décision du 26 avril 2006, le département a admis les oppositions, refusé la dérogation et ordonné la remise en état des locaux "dans les trois mois qui sui[ven]t l'entrée en force de la présente décision". Le 29 mai 2006, la commune de Travers a formellement refusé le permis de construire et ordonné la remise en état des lieux conformément à la décision du 26 avril 2006. A._ et B._ ont recouru contre ces deux décisions auprès du Conseil d'Etat du canton de Neuchâtel, qui a rejeté les recours par décision du 21 novembre 2007.
A._ et B._ ont alors contesté cette décision devant le Tribunal administratif du canton de Neuchâtel, Cour de droit public (ci-après: le Tribunal administratif). Leur recours a été rejeté par arrêt du 27 novembre 2008. Le Tribunal administratif a considéré en substance que l'atelier litigieux impliquait un changement complet d'affectation, que les conditions pour l'octroi d'une autorisation n'étaient pas remplies et que les recourants ne pouvaient bénéficier ni des règles sur la protection de la bonne foi ni de celles sur l'égalité de traitement. Enfin, il a estimé que l'autorité n'était pas déchue du droit d'exiger la remise en état, qui respectait le principe de la proportionnalité.
C. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral d'annuler cet arrêt. Ils se plaignent d'une violation de leur droit d'être entendus (art. 29 al. 2 Cst.), d'une appréciation arbitraire des preuves (art. 9 Cst.) ainsi que d'une violation des art. 24 et 24a de la loi fédérale sur l'aménagement du territoire du 22 juin 1979 (LAT; RS 700). Ils requièrent également l'octroi de l'effet suspensif. D._ et C._ ainsi que la commune de Val-de-Travers se sont déterminés; ils concluent au rejet du recours. Le Tribunal administratif conclut également au rejet du recours, en se référant aux considérants de son arrêt. L'Office fédéral du développement territorial a renoncé à présenter des observations.
D. Par ordonnance du 2 février 2009, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif.
E. Le 1er mai 2009, A._ et B._, agissant seuls, ont présenté spontanément des observations complémentaires et déposé de nouvelles pièces. L'intimé D._ est décédé le 30 juin 2009.

Considérant en droit:
1. Dirigé contre une décision rendue dans le domaine du droit public de l'aménagement du territoire et des constructions, le recours est recevable comme recours en matière de droit public conformément aux <ref-law> et 34 al. 1 LAT dans sa teneur actuelle selon le ch. 64 de l'annexe à la loi sur le Tribunal administratif fédéral (ATF 133 Il 353 consid. 2 p. 356, 249 consid. 1.2 p. 251). Aucune des exceptions prévues à l'<ref-law> n'est réalisée. Les recourants ont pris part à la procédure de recours devant le Tribunal administratif et sont particulièrement touchés par l'arrêt attaqué, qui confirme l'ordre de remise en état de leur construction. Ils ont donc la qualité pour agir au sens de l'<ref-law>. Pour le surplus, interjeté en temps utile contre une décision finale prise en dernière instance cantonale non susceptible de recours devant le Tribunal administratif fédéral, le recours est recevable (art. 86 al. 1 let. d, 90 et 100 al. 1 LTF).
L'intimé D._ est décédé le 30 juin 2009. En principe, le procès est suspendu lors du décès d'une partie et reprend lorsque la succession ne peut plus être répudiée ou que la liquidation officielle a été instituée, sous réserve d'une reprise anticipée de procès urgents par le représentant de la succession (art. 6 al. 2 et 3 PCF, applicable par renvoi de l'<ref-law>). Il y a lieu de faire exception dans le cas d'espèce, dès lors que l'épouse de l'intimé décédé est elle-même partie au procès et dans la mesure où la disparition de l'intimé en question est sans incidence sur l'issue du litige, notamment en terme de frais et dépens (cf. infra consid. 6).
2. Les recourants ont spontanément présenté des observations complémentaires le 1er mai 2009, soit après l'échéance du délai de recours. A l'appui de celles-ci, ils ont produit de nouvelles pièces, à savoir pour l'essentiel des documents relatifs à la réalisation de l'atelier litigieux au début des années 1990. Ils n'expliquent cependant pas la portée de ces pièces au regard des faits constatés dans l'arrêt querellé, ni en quoi ces documents pourraient "résulter de la décision attaquée" au sens de l'<ref-law>. Il n'y a dès lors pas lieu de les prendre en compte (<ref-law>; <ref-ruling> consid. 3 p. 395).
3. Invoquant l'art. 29 al. 2 Cst. les recourants affirment que le Tribunal administratif aurait violé leur droit d'être entendus, en refusant d'entendre des témoins dont ils avaient requis l'audition.
3.1 Le droit d'être entendu, tel qu'il est garanti à l'art. 29 al. 2 Cst., comprend notamment le droit pour l'intéressé de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuve pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 2.2 p. 504 s.; <ref-ruling> consid. 2b p. 56; <ref-ruling> consid. 3a p. 51 et les arrêts cités). L'autorité peut cependant renoncer à procéder à des mesures d'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 2.1 p. 429; <ref-ruling> consid. 6c/cc in fine p. 135; <ref-ruling> consid. 4a p. 211 et les arrêts cités).
3.2 En l'espèce, les recourants demandaient l'audition de plusieurs témoins pour démontrer que les autorités connaissaient l'existence de leur atelier depuis sa construction et qu'ils avaient obtenu des assurances quant au fait qu'il serait autorisé, de sorte qu'ils pouvaient se prévaloir de la protection de la bonne foi (respect des promesses). Le Tribunal administratif a considéré qu'il n'était pas nécessaire d'examiner ces questions, car les droits des voisins concernés faisaient obstacle à l'application du principe de la bonne foi.
Cette appréciation anticipée des preuves est dénuée d'arbitraire. En effet, on admet généralement que l'intérêt à la protection de la bonne foi peut céder devant un intérêt public supérieur ou devant l'intérêt lié à l'application correcte du droit; il peut dans ce cadre être mis en balance avec l'intérêt de tiers, tel que celui des voisins qui seraient touchés par l'admission d'une situation contraire au droit des constructions pour des motifs de protection de la bonne foi (Georg Müller, in Aubert et al. (éd.), Commentaire de la Constitution fédérale de la Confédération suisse du 29 mai 1874, 1993, n. 68 ad. art. 4; Arthur Haefliger, Alle Schweizer sind vor dem Gesetze gleich, 1985, p. 225). Selon un principe reconnu en droit public des constructions, les indications favorables données par l'autorité au seul propriétaire ne peuvent pas être opposées aux tiers qui s'en prennent à l'octroi d'une autorisation de construire. On considère en effet que le maître de l'ouvrage doit savoir qu'une construction est soumise à l'enquête publique et qu'il ne peut pas penser de bonne foi qu'une indication ou un renseignement de l'autorité implique une décision par anticipation sur la procédure d'opposition ou de recours. Ainsi, lorsque la loi institue des possibilités formelles de participation ou de recours pour la protection des tiers, il n'y a plus de place pour les assurances qui seraient données hors des procédures prescrites et qui excluraient cette protection juridique (<ref-ruling> consid. 3e p. 290 s.; Béatrice Weber-Dürler, Falsche Auskünfte von Behörden, in ZBl 1/1991, p. 17 et les références; Béatrice Weber-Dürler, Vertrauensschutz im öffentlichen Recht, 1983, p. 148 s.). Dans ces conditions, même si des témoins avaient pu confirmer que des assurances avaient été données aux recourants, celles-ci ne seraient de toute manière pas opposables aux intimés, en leur qualité de voisins directs. C'est dès lors sans arbitraire que le Tribunal administratif a écarté l'audition de ces témoins, de sorte que ce premier moyen doit être rejeté.
4. Dans un grief connexe, les recourants reprochent à l'autorité cantonale d'avoir rendu une décision arbitraire en écartant plusieurs témoignages qui auraient pu, selon eux, fonder la protection de la bonne foi. Cette argumentation n'a cependant pas de portée indépendante de celle qui vient d'être examinée. En effet, les recourants voient un arbitraire dans le fait que la décision a été rendue sans tenir compte de témoignages écartés en raison d'une appréciation anticipée des preuves. Or, comme on vient de le voir, cette appréciation anticipée n'est pas arbitraire, si bien que la décision rendue sans ces témoignages n'est arbitraire ni dans sa motivation ni dans son résultat.
5. Les recourants se plaignent pour le surplus d'une violation de la loi fédérale sur l'aménagement du territoire. Ils prétendent en substance que l'implantation de l'atelier litigieux hors de la zone à bâtir doit être autorisée sur la base de l'art. 24 LAT en raison des conséquences dommageables que la fermeture de l'atelier entraînerait pour eux, le changement d'affectation n'ayant en outre aucune incidence sur le territoire, l'équipement ou l'environnement, au sens de l'art. 24a LAT.
5.1 L'atelier litigieux ayant été réalisé sans autorisation, il doit en principe faire l'objet d'un ordre de remise en état. Selon la jurisprudence, l'autorité peut toutefois renoncer à ordonner une telle mesure si les dérogations à la règle sont mineures, si l'intérêt public lésé n'est pas de nature à justifier le dommage que la démolition causerait au maître de l'ouvrage, si celui-ci pouvait de bonne foi se croire autorisé à construire ou encore s'il y a des chances sérieuses de faire reconnaître la construction comme conforme au droit; celui qui place l'autorité devant le fait accompli doit cependant s'attendre à ce qu'elle se préoccupe plus de rétablir une situation conforme au droit que d'éviter les inconvénients qui en découlent pour lui (<ref-ruling> consid. 4 p. 255; <ref-ruling> consid. 6b p. 224; <ref-ruling> consid. 4 p. 217; arrêt 1A.180/2002 du 19 novembre 2002 consid. 3.1 publié in SJ 2003 I p. 271). En l'occurrence, il y a lieu d'examiner si l'atelier litigieux est conforme au droit, comme le prétendent les recourants. Il n'est pas contesté que l'atelier en cause ne peut être autorisé sous la forme d'une autorisation ordinaire, puisqu'il n'a aucune vocation agricole ni aucun lien avec une exploitation agricole ou horticole existante. Il convient cependant d'examiner s'il peut être autorisé sur la base des art. 24 et 24a LAT invoqués par les recourants.
5.2 Selon la jurisprudence, une construction est imposée par sa destination au sens de l'art. 24 let. a LAT lorsqu'elle est adaptée aux besoins qu'elle est censée satisfaire et qu'elle ne peut remplir son rôle que si elle est réalisée à l'endroit prévu: une nécessité particulière, tenant à la technique, aux conditions d'exploitation d'une entreprise, ou encore à la configuration ou à la nature du sol, doit imposer le choix de l'endroit. De même, l'implantation hors de la zone à bâtir peut se justifier si l'ouvrage en question ne peut être édifié à l'intérieur de celle-ci en raison des nuisances qu'il occasionne. Seuls des critères objectifs sont déterminants, à l'exclusion de points de vue subjectifs du constructeur ou de motifs de convenance personnelle (<ref-ruling> consid. 3.1. p. 68; <ref-ruling> consid. 5a p. 261, 499 consid. 3b/cc p. 508 et les arrêts cités).
En l'espèce, les recourants ne peuvent pas se prévaloir d'une nécessité impérieuse d'installer leur atelier à l'endroit où il se trouve actuellement. Ils reconnaissent d'ailleurs qu'il pourrait "en théorie, parfaitement être implanté ailleurs". Ils invoquent cependant des "conséquences extrêmement sérieuses" pour l'entreprise du recourant ainsi que pour l'organisation de leur vie de famille en cas de remise en état. Ces éléments relèvent toutefois du point de vue subjectif des constructeurs et de leur convenance personnelle, de sorte qu'ils ne peuvent pas être pris en considération selon la jurisprudence susmentionnée. Il y a donc lieu de constater que le Tribunal administratif n'a pas violé l'art. 24 let. a LAT en considérant que l'implantation de l'installation litigieuse n'était pas imposée par sa destination.
5.3 Aux termes de l'art. 24a al. 1 LAT, lorsque le changement d'affectation de constructions et d'installations sises hors de la zone à bâtir ne nécessite pas de travaux de transformation au sens de l'art. 22 al. 1 LAT, l'autorisation doit être accordée aux conditions suivantes: ce changement d'affectation n'a pas d'incidence sur le territoire, l'équipement et l'environnement (let. a); il ne contrevient à aucune autre loi fédérale (let. b). En l'occurrence, comme l'a relevé la Cour cantonale, les recourants eux-mêmes ne nient pas que l'exploitation d'un atelier de serrurerie dans leur bâtiment entraîne un accroissement du trafic - sans rapport avec l'agriculture - dans la zone où il est implanté. De plus, il est vraisemblable qu'il entraîne également des nuisances sonores, ce que les divers opposants ont mentionné à plusieurs reprises au cours de la procédure sans être contredits sur ce point par les recourants. Dans ces circonstances, on ne saurait considérer que l'installation litigieuse n'a aucune incidence sur le territoire, l'équipement ou l'environnement, de sorte que les conditions d'application de l'art. 24a al. 1 ne sont pas remplies. Par conséquent, les recourants ne peuvent être mis au bénéfice d'une autorisation sur la base de cette disposition.
6. Il s'ensuit que le recours doit être rejeté. Les recourants, qui succombent, doivent supporter les frais de la présente procédure (<ref-law>). Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge des recourants.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué au mandataire des recourants, aux intimés, à la Commune de Val-de-Travers, au Conseil d'Etat et au Tribunal administratif du canton de Neuchâtel, ainsi qu'à l'Office fédéral du développement territorial.
Lausanne, le 24 août 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener