Faits: A. Depuis les années 1920, et jusqu'en 1962, des chalets de vacances ont été érigés par des privés sur la rive sud du lac de Neuchâtel, dans le domaine public de l'Etat de Fribourg, sur la base de concessions ou autres autorisations à bien plaire. La rive sud du lac de Neuchâtel ("Grande Cariçaie") figure sur différents inventaires fédéraux, sur celui des paysages, sites et monuments naturels depuis 1983, sur celui des réserves d'oiseaux d'eau et de migrateurs d'importance internationale et nationale depuis 1991, sur celui des zones alluviales d'importance nationale depuis 1992, sur celui des bas-marais d'importance nationale depuis 1994 et sur celui des sites marécageux d'une beauté particulière et d'importance nationale depuis 1996. B. Face au développement des chalets de vacances, le Conseil d'Etat du canton de Fribourg a adopté, le 1er juin 1982, le "plan directeur de la rive sud du lac de Neuchâtel et des rives du lac de Morat" (ci-après: le plan directeur de 1982), prévoyant la suppression progressive, au fur et à mesure de l'expiration de la durée des autorisations d'utilisation du terrain public, de toutes les résidences secondaires sises dans les zones protégées. Un arrêté du Conseil d'Etat du canton de Fribourg du 26 avril 1983 "instaurant des mesures concernant les maisons de vacances sur le domaine public et privé de l'Etat au bord du lac de Neuchâtel" et complétant ce plan directeur, prévoyait que les autorisations d'utiliser le domaine public à l'intérieur des périmètres des zones naturelles étaient incessibles et non renouvelables et qu'elles arriveraient à échéance le 31 décembre 1998. Ce délai a toutefois été repoussé au 31 décembre 2008 par arrêté du 24 juin 1997. C. Le 6 mars 2002, la Direction des travaux publics de l'Etat de Fribourg (actuellement la Direction de l'aménagement, de l'environnement et des constructions) a adopté un "plan d'affectation cantonal des réserves naturelles sur la rive sud du lac de Neuchâtel". Ce plan d'affectation ne règle pas expressément le sort des chalets de vacances, mais réserve à ce sujet "la législation spéciale". En date du 27 novembre 2007, le Conseil d'Etat a édicté une ordonnance abrogeant l'arrêté du 26 avril 1983 et instituant un "contrat nature" permettant la pérennisation des chalets. Moyennant la signature d'un "contrat nature" avec l'Etat de Fribourg, chaque actuel propriétaire de chalet pourra continuer à occuper les lieux sa vie durant, et après lui son conjoint ou partenaire enregistré et leurs descendants en ligne directe. Le 27 novembre 2007 également, le Conseil d'Etat a modifié le plan directeur de 1982, en ce que l'obligation de suppression progressive des chalets de vacances a été complétée par la mention "sous réserve de la conclusion de contrats nature selon l'ordonnance du 27 novembre 2007". D. Le 24 janvier 2008, l'Association suisse pour la protection des oiseaux (ci-après: l'ASPO), Pro Natura, Pro Natura Fribourg, le WWF Suisse et le WWF Fribourg ont recouru auprès de la IIème Cour administrative du Tribunal cantonal du canton de Fribourg (ci-après: le Tribunal cantonal) contre l'ordonnance du Conseil d'Etat du 27 novembre 2007 "relative à l'établissement d'un contrat nature pour les chalets de vacances sur le domaine de l'Etat au bord du lac de Neuchâtel" et contre l'arrêté du Conseil d'Etat du 27 novembre 2007 modifiant le "plan directeur de la rive sud du lac de Neuchâtel et des rives du lac de Morat", dans la mesure où ces deux actes portent sur les chalets de vacances sis sur le domaine de l'Etat de Fribourg, à l'intérieur des réserves naturelles dans les communes de Font, Forel et Delley-Portalban. Par arrêt du 12 août 2008, le Tribunal cantonal a déclaré le recours irrecevable. Il a considéré en substance que l'ordonnance et l'arrêté litigieux n'étaient pas des décisions susceptibles de recours mais des actes généraux et abstraits. Le droit fribourgeois ne connaissant pas le contrôle abstrait des normes, le recours devait être déclaré irrecevable. E. Agissant par la voie du recours en matière de droit public, l'ASPO, Pro Natura, Pro Natura Fribourg, le WWF Suisse et le WWF Fribourg (ci-après: les recourants ou l'ASPO et consorts) demandent au Tribunal fédéral d'annuler l'arrêt du Tribunal cantonal et de retourner le dossier à celui-ci pour qu'il statue sur le fond du recours du 24 janvier 2008. Les recourants estiment que les deux actes litigieux ont un caractère décisionnel et que dès lors la compétence du Tribunal cantonal est donnée. Le Conseil d'Etat conclut au rejet du recours. Se référant aux considérants de l'arrêt attaqué, le Tribunal cantonal conclut également au rejet du recours. Invité à se déterminer, l'Office fédéral de l'environnement conclut implicitement à l'admission du recours. Par courrier du 16 mars 2009, les recourants ont persisté dans leurs conclusions. F. Par ordonnance du 5 décembre 2008, le Président de la Ire Cour de droit public a rejeté la requête de suspension de la procédure, formulée par les recourants qui invoquent l'existence de procédures judiciaires pendantes dans le canton de Vaud où la question du statut des chalets de vacances sur la rive sud du lac de Neuchâtel est également litigieuse. 