Faits:
A. A._ était propriétaire des parcelles n°s 4779 et 6542 du cadastre de la commune de Cortaillod, respectivement d'une surface de 3'000 et de 6'514 m2. Il avait acquis la première en 1967. Quant à la seconde, elle était constituée de l'ancien article 4831, acquis en 1968 ainsi que de 1'882 m2 provenant de l'ancien article 4829, achetés en 1998.
Selon le plan d'aménagement communal de 1965 et son règlement correspondant, l'actuelle parcelle n° 6542 était sise en zone de grève ONC (ordre non contigu) IV et la parcelle n° 4779 en zone ONC III. Suite à la modification du plan d'aménagement en 1975, ces deux articles ont été colloqués en zone d'utilisation différée.
Le nouveau plan d'aménagement sanctionné par le Conseil d'Etat le 27 octobre 1999 a classé la majeure partie des parcelles n°s 6542 (soit 5'975 m2) et 4779 (soit 2'673 m2) en zone d'urbanisation, plus particulièrement en zone touristique.
B. Par décision du 8 novembre 2004, le Département de la gestion du territoire (ci-après: le département) a respectivement fixé à 103'965 et à 26'997 fr. 30, les contributions dues par A._ à la suite du changement d'affectation des parcelles n°s 6542 et 4779.
A._ a recouru contre ce prononcé auprès du Tribunal administratif de la République et canton de Neuchâtel (ci-après: le Tribunal administratif). Par arrêt du 13 août 2007, cette autorité a admis partiellement le recours. Elle a annulé la décision entreprise, en tant qu'elle concernait l'article 6542, la cause étant renvoyée au département pour complément d'instruction et nouvelle décision éventuelle sur ce point. Elle a rejeté le recours pour le surplus.
Le Tribunal administratif a estimé que la zone d'utilisation différée, à tout le moins dans le secteur en question, ne devait pas être considérée comme une zone à bâtir. L'attribution des deux parcelles à la zone touristique, constructible, constituait donc bien une mesure entraînant un avantage majeur. Par ailleurs, le fait que ces dernières aient antérieurement été classées en zone constructible n'était pas déterminant. S'agissant de la parcelle n° 6542, la Cour cantonale a relevé qu'il n'était pas contesté que la servitude qui la grevait n'autorisait que la construction de maisons à caractère familial, ce qui faisait obstacle à une valorisation compte tenu des exigences de la zone touristique. A moins d'un accord entre les propriétaires des fonds dominant et servant, la mesure d'aménagement était sans effet sur la constructibilité du bien-fonds. Il ne ressortait pas du dossier qu'un accord ait été envisagé ou qu'il ait été sur le point d'aboutir. Cette question n'avait d'ailleurs pas fait l'objet d'un véritable examen, de sorte que la cause devait être retournée au département pour instruction.
A._ est décédé le 21 novembre 2006.
C. Agissant par la voie du recours en matière de droit public, les héritiers de A._, soit B._, D._ et C._, ainsi que E._, avocat agissant en qualité d'exécuteur testamentaire, demandent au Tribunal fédéral d'annuler l'arrêt rendu par le Tribunal administratif le 13 août 2007 et de dire qu'aucune indemnité pour plus-value n'est due pour l'article 4779. Subsidiairement, ils requièrent que la cause soit renvoyée au Tribunal administratif pour nouvelle décision dans le sens des considérants. Ils se plaignent d'une violation de l'art. 5 de la loi fédérale sur l'aménagement du territoire (LAT). Ils invoquent en outre le principe de l'interdiction de l'arbitraire ainsi que le droit d'être entendu, en particulier le droit à une décision motivée.
Le Tribunal administratif et le département concluent au rejet du recours. L'Office fédéral du développement territorial a indiqué que l'affaire ne soulevait pas, au regard du droit fédéral de l'aménagement et de la planification, de questions de principe nécessitant des observations de sa part.

Considérant en droit:
1. Le recours est dirigé contre une décision de plus-value, qui est une décision fondée, en tout cas partiellement, sur le droit public fédéral (<ref-ruling> consid. 1 p. 573 ss). Il est donc recevable comme recours en matière de droit public au sens des <ref-law> et 34 al. 1 de la loi fédérale du 22 juin 1979 sur l'aménagement du territoire (RS 700; LAT) dans sa teneur actuelle selon le ch. 64 de l'annexe à la loi sur le Tribunal administratif fédéral. Aucune des exceptions mentionnées à l'<ref-law> n'est réalisée.
S'agissant d'un procès concernant le passif de la succession, l'exécuteur testamentaire a qualité pour le conduire en son propre nom et en tant que partie à la place de celui qui est, quand au fond, le sujet actif ou passif du droit contesté (arrêt 5P.355/2006 du 8 novembre 2006 consid 3.1; <ref-ruling> consid. 3 p. 133 s.). L'exécuteur testamentaire dispose dès lors de la qualité pour recourir (<ref-law>). Dans ces conditions, la qualité pour recourir des héritiers peut demeurer indécise.
2. En tant que l'arrêt attaqué renvoie la cause à l'autorité inférieure pour nouvelle décision quant à la parcelle n° 6542, il s'agit d'une décision incidente qui ne peut faire l'objet d'un recours immédiat qu'aux conditions de l'<ref-law>, qui ne sont manifestement pas remplies en l'espèce.
Le recours est cependant uniquement dirigé contre la confirmation de la perception de la plus-value pour l'article 4779. Sur ce point, le prononcé entrepris revêt la qualité de décision partielle au sens de l'<ref-law> (cf. <ref-ruling>). Le recours est dès lors recevable contre une telle décision.
3. Les recourants se plaignent d'une violation de leur droit d'être entendus. Ils estiment que l'autorité cantonale aurait violé son obligation de motivation en se référant à un arrêt du Tribunal fédéral du 27 novembre 2006.
3.1 Le Tribunal administratif a considéré que le fait que les parcelles en cause avaient été affectées à la zone constructible, antérieurement à leur attribution à la zone d'utilisation différée, n'était pas déterminant. Il a déclaré que ce point avait été tranché et confirmé par le Tribunal fédéral par arrêt du 27 novembre 2006. Il a encore précisé que chaque mesure d'aménagement pouvait donner lieu à une compensation lorsqu'elle constituait soit un avantage soit un inconvénient majeur.
Dans sa décision relative à la perception de la plus-value, le département avait fait valoir que selon l'art. 34 al. 2 de la loi cantonale du 2 octobre 1991 sur l'aménagement du territoire (LCAT), la plus-value était la différence présumée entre la valeur du bien-fonds avant et après la mesure d'aménagement. D'ailleurs, en matière d'expropriation matérielle, il n'était nullement tenu compte des plans abrogés antérieurement. Dans ses observations, le département a encore précisé que les recourants se référaient à un plan antérieur qui n'était pas conforme à la loi fédérale sur l'aménagement du territoire car il comprenait une zone à bâtir largement surdimensionnée. Il était dès lors exclu de s'y référer.
3.2 En l'occurrence, s'il est vrai que la référence à l'arrêt du Tribunal fédéral du 27 novembre 2006 est injustifiée (cf. consid. 4.3), il n'en résulte pas que le Tribunal administratif aurait de ce seul fait manqué à son obligation de motivation. Pour le surplus, l'argumentation de la Cour cantonale est certes laconique, mais les recourants pouvaient comprendre que l'autorité n'avait pas tenu compte de l'affectation de la parcelle en cause à une zone constructible avant l'entrée en vigueur de la LAT, pour les motifs exposés par le département dans sa décision, puis explicités dans ses observations.
4. Sur le fond, il n'est pas contesté que la parcelle n° 4779 n'était pas constructible tant qu'elle était colloquée en zone d'utilisation différée (1975-1999) et qu'elle l'est devenue par son affectation à la zone touristique. Les recourants reprochent en revanche au Tribunal administratif de ne pas avoir pris en considération le fait que leur parcelle était constructible au moment de son acquisition (1967). La Cour cantonale s'écarterait de sa jurisprudence antérieure (arrêt non publié du Tribunal administratif du 27 septembre 1989).
4.1 L'art. 5 al. 1 LAT prévoit que le droit cantonal doit établir un régime de compensation permettant de tenir compte équitablement des avantages et des inconvénients majeurs qui résultent des mesures d'aménagement. La notion d'avantage majeur est ainsi une notion de droit fédéral. Il s'agit toutefois d'une notion juridique indéterminée, de sorte qu'il faut laisser à la juridiction cantonale une certaine latitude de jugement (cf. notamment Enrico Riva, Commentaire LAT, art. 5 n. 84). Le Tribunal fédéral a récemment précisé que l'avantage majeur devait être de nature économique et s'apprécier selon l'ensemble des circonstances (<ref-ruling> consid. 2.1 p. 402 s.).
4.2 La réglementation neuchâteloise (art. 33 ss LCAT) a été mise en place suite à l'entrée en vigueur, le 1er janvier 1980, de l'art. 5 al. 1 LAT. Selon l'art. 33 LCAT, les avantages et les inconvénients résultant de mesures d'aménagement du territoire font l'objet d'une compensation s'ils sont majeurs. L'augmentation de valeur d'un bien-fonds consécutive à son affectation à la zone d'urbanisation (art. 47) ou à une zone spécifique (art. 53) est réputée avantage majeur constituant une plus-value (art. 34 al. 1 LCAT). Celle-ci est la différence présumée entre la valeur d'un bien-fonds avant et après la mesure d'aménagement (art. 34 al. 2 LCAT). En cas de plus-value, une contribution correspondant à 20 % de celle-ci est due à l'Etat par le propriétaire du bien-fonds (art. 35 al. 1 LCAT).
La présomption de l'art. 34 al. 1 LCAT est réfragable (arrêt du Tribunal administratif du 24 février 2003 paru à la RJN 2003 360 et les arrêts cités). La jurisprudence cantonale a également posé que le caractère majeur de l'avantage procuré par la mesure d'aménagement doit être apprécié au regard de la variation réelle et concrète de la valeur de l'immeuble en cause et non dans l'abstrait. Est déterminante la possibilité effective d'utiliser la parcelle pour la construction d'une manière conforme à la zone dont elle fait désormais partie (ibid.). Il faut tenir compte, équitablement, dans le cas concret, des avantages et inconvénients majeurs tels qu'ils résultent de l'ensemble des circonstances propres à la mesure d'aménagement considérée (arrêt du Tribunal administratif du 17 février 1994 paru à la RJN 1994 167). La doctrine et la jurisprudence ont en outre interprété l'art. 34 al. 2 LCAT en ce sens que c'est la valeur objective du terrain qui doit être prise en considération (Francesco Parrino, La contribution sur la plus-value dans le canton de Neuchâtel in Mémoire ASPAN n° 57, Berne 1992, p. 46; arrêt du Tribunal administratif du 24 février 2003 paru à la RJN 2003 360).
4.3 Dans un arrêt du 25 février 2002 concernant la commune de Boudry, le Tribunal administratif avait jugé que l'affectation en zone d'urbanisation de parcelles sises en zone agricole depuis 1979 ne s'opposait pas à la perception d'une contribution de plus-value, quand bien même ces dernières étaient constructibles au moment de leur acquisition, en vertu d'un plan datant de 1966. Chaque mesure d'aménagement pouvait en effet donner lieu à une compensation lorsqu'elle constituait soit un avantage, soit un inconvénient majeurs.
Contrairement à ce qu'affirme l'autorité cantonale, cette décision n'a pas été confirmée par le Tribunal fédéral, l'arrêt rendu le 27 novembre 2006 n'ayant porté que sur la problématique de la prise en compte de la distance légale de 30 mètres à la forêt.
4.4 Les recourants font quant à eux référence à un arrêt rendu le 27 septembre 1989 par le Tribunal administratif neuchâtelois, qui n'a été ni publié ni communiqué au Tribunal de céans par les recourants mais qui est mentionné par la doctrine (Piermarco Zen-Ruffinen/ Christine Guy-Ecabert, Aménagement du territoire, construction, expropriation, Berne 2001, p. 79). L'autorité cantonale aurait considéré que ne constituait pas un avantage majeur l'affectation en zone à bâtir d'un terrain, acheté en 1975 comme terrain à bâtir mais placé par la suite en zone non constructible (d'octobre 1986 à février 1988), au motif que les mesures d'aménagement prises en 1988 n'auraient pas augmenté la valeur du bien-fonds.
Les recourants estiment que cette jurisprudence devrait leur être pleinement appliquée au vu de la rapide succession des affectations. Il apparaît au contraire que les deux situations ne sont en rien comparables. En effet, on ignore si le plan autorisant antérieurement la construction était conforme à la LAT. Surtout, la collocation en zone non constructible avait duré moins de deux ans, contre plus de 20 en l'occurrence.
4.5 L'art. 5 al. 1 LAT ne vise pas seulement les mesures d'aménagement mises en oeuvre depuis l'entrée en vigueur de la LAT et approuvées par l'autorité cantonale selon l'art. 26 LAT (dfjp/ofat, Recommandations concernant le régime de la compensation des avantages résultant de mesures d'aménagement selon l'article 5, premier alinéa, de la loi fédérale sur l'aménagement du territoire, novembre 2006, p. 8; Bernhard Waldmann/Peter Hänni, Raumplanungsgesetz, Berne 2006, ad art. 5, n° 11). Le régime de compensation s'étend ainsi également à toutes les mesures d'aménagement conformes au mandat constitutionnel donné par l'ancien article 22quater Cst., entré en vigueur en 1969 et prescrivant déjà une utilisation judicieuse et mesurée du sol, ainsi qu'une occupation rationnelle du territoire (Jean-François Aubert/Pascal Mahon, Petit commentaire de la Constitution fédérale de la Confédération suisse du 18 avril 1999, Zurich Bâle Genève 2003, ad art. 75 n° 6).
Selon l'art. 15 LAT, les zones à bâtir comprennent les terrains propres à la construction, qui sont soit déjà largement bâtis, ou qui seront nécessaires à la construction dans les quinze ans à venir et équipés dans ce laps de temps. Une zone à bâtir est ainsi largement surdimensionnée lorsque sa surface excède ce qui est probablement nécessaire à la construction dans les quinze années à venir, au sens de l'art. 15 let. b LAT (<ref-ruling> consid. 2b p. 252 s.). Il est acquis qu'il existe un intérêt public important à mettre en oeuvre cette disposition et à réduire l'étendue des anciennes zones à bâtir surdimensionnées (cf. notamment <ref-ruling> consid. 3b p. 231).
En l'espèce, le secteur concerné n'était pas largement bâti. Le département soutient au surplus que le plan de 1965 comprenait une zone à bâtir trop importante. Il est en effet admis que la création de zones de réserve hors de la zone à bâtir (art. 18 al. 2 LAT) est un moyen de répondre à l'exigence de réduire la surface des zones surdimensionnées (Piermarco Zen Ruffinen/Christine Guy-Ecabert, op. cit., p. 154). Dans ces circonstances, l'affectation de la parcelle à la zone d'utilisation différée en 1975 n'était que l'expression d'une adaptation de la situation au nouveau mandat constitutionnel. Ainsi, la confirmation de l'existence d'un avantage majeur par l'autorité cantonale dans le cas particulier, au motif que les recourants ne sauraient tirer profit d'une affectation antérieure contraire au droit, ne peut en tout cas pas être qualifiée d'insoutenable.
4.6 Comme cela a été rappelé ci-dessus, l'avantage majeur doit toutefois être de nature économique (cf. consid. 4.1). Les recommandations du DFJP et de l'OFAT précisent d'ailleurs que la valeur de comparaison inférieure servant à calculer la plus-value imposable doit être la valeur au moment de la dernière réalisation déterminante au sens de la contribution sur les avantages (dfjp/ofat, op. cit., p. 21 s.). Par ailleurs, l'avantage majeur doit impérativement s'apprécier selon l'ensemble des circonstances (cf. consid. 4.1). En outre, il ne faut pas perdre de vue que le principe de l'équité est à la base du système de compensation des avantages (Message du Conseil fédéral concernant la LAT, FF 1978 I 1007 p. 1018).
Dans le cas particulier, le département n'a toutefois pas retenu le prix, correspondant à celui de la zone agricole, évalué à 4 fr. le m2 par les experts. En effet, il a augmenté ce montant à 30 fr. le m2, notamment en raison du fait que d'éventuels acquéreurs pouvaient supposer que les terrains concernés seraient prioritairement affectés à la zone à bâtir, puisqu'ils se trouvaient hors de la zone à bâtir, mais à l'intérieur du périmètre de localité. Ce dernier élément peut d'ailleurs expliquer leur collocation initiale en zone à bâtir erronée. Les autorités cantonales ont ainsi correctement pris en considération la situation particulière des parcelles.
La contribution de plus-value telle que fixée dans le cas d'espèce ne saurait par conséquent être considérée comme contraire à l'art. 5 LAT.
5. Il s'ensuit que le recours doit être rejeté. Les recourants, qui succombent, doivent supporter l'émolument judiciaire (<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, au Département de la gestion du territoire et au Tribunal administratif de la République et canton de Neuchâtel ainsi qu'à l'Office fédéral du développement territorial.
Lausanne, le 28 janvier 2008
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Féraud Truttmann