Faits: A. A._ et B._ sont propriétaires des parcelles 556 et 557 de la commune de St-Sulpice, à proximité immédiate du port des Pierrettes. Sur la première parcelle se trouve une villa alors que la seconde supporte huit anciens cabanons de pêcheurs. C._ et consorts sont propriétaires de ces cabanons. La parcelle 564, qui jouxte la parcelle 557, comporte sept cabanons de même type. B. Le plan directeur de la commune de St-Sulpice du 26 septembre 1997 retient, dans les mesures d'aménagement relatives au Port des Pierrettes, ce qui suit: «A proximité du port, respecter l'esprit du "village de pêcheurs" par une implantation resserrée de bâtiments de petites dimensions dont les matériaux s'apparentent à ceux des constructions existantes» et «Encourager la mixité habitat - travail où les activités sont en relation avec les bateaux, les sports nautiques, la pêche ou le tourisme. Poursuivre l'ambiance du "village de pêcheur"» (Fiche 7.2.40, ch. 141 et 340). Sur cette base, la Municipalité de St-Sulpice a entrepris une réflexion en vue d'assurer une protection de l'ensemble des cabanons de pêcheurs situés sur les parcelles 564 et 557 et a commencé à élaborer un plan partiel d'affectation. Dans ce contexte, une expertise a été requise de X._, conservatrice au Musée du Léman à Nyon. Dans un rapport du 15 décembre 1999, celle-ci a indiqué que l'ensemble de pêcheries du site du port des Pierrettes présentait un caractère suffisamment exceptionnel pour figurer à l'inventaire du patrimoine lémanique. Dans un préavis du 30 mars 2000, le conservateur cantonal des monuments historiques s'est rallié à l'appréciation faite dans le rapport précité. Le 28 septembre 2001, un rapport d'expertise émanant de Y._, expert de l'Office fédéral de la culture, a confirmé l'importance du site méritant sauvegarde. Il a exposé que, compte tenu de sa dimension, de sa situation par rapport au lac et de sa densité, ce quartier constituait un établissement unique sur les rives des lacs suisses. C. A._ et B._ souhaitant construire une villa sur leurs parcelles, ils ont résilié les baux d'emplacement des cabanons sis sur la parcelle 557 avec effet au 31 décembre 2000. Par arrêt du 11 décembre 2001, le Tribunal fédéral a confirmé que les contrats de bail à loyer avaient été valablement résiliés. Il a notamment été constaté que l'objet des baux passés entre les parties avait exclusivement trait au terrain nu; les cabanons, constructions mobilières, n'appartenaient pas aux propriétaires du terrain mais aux locataires. Depuis la résiliation des contrats, les cabanons sont inoccupés. A._ et B._ ont obtenu du Juge de paix une défense publique de pénétrer sur la parcelle 557. En juillet 2000, ils ont déposé une demande de permis de construire tendant à la démolition d'un pavillon, au démontage de huit cabanons et à la construction d'une villa avec garage indépendant sur les deux parcelles 556 et 557 réunies. La Municipalité de St-Sulpice a refusé le permis requis le 29 novembre 2000, en se référant notamment à l'opposition du Département cantonal des infrastructures du canton de Vaud (ci-après: le Département des infrastructures), lequel faisait valoir que les cabanons devaient être conservés et protégés au titre de témoignages de pratiques vivantes de l'époque en tant que cabanons de pêcheurs. Le recours de A._ et B._ contre cette décision a été rejeté par le Tribunal administratif du canton de Vaud (actuellement la Cour de droit administratif et public du Tribunal cantonal; ci-après: le Tribunal cantonal) le 12 juillet 2006. D. Par décision du 20 mars 2002, le Département des infrastructures a procédé au classement du site du port des Pierrettes, en vue d'en assurer la sauvegarde et la conservation. La mesure s'étendait au port traditionnel et aux anciens cabanons de pêcheurs qui le bordaient sur son flanc nord. A l'intérieur de ce périmètre, les cabanons devaient être conservés à leurs emplacements actuels. Ils devaient être entretenus et pouvaient être aménagés, dans la mesure où les travaux ne portaient pas atteinte au caractère des constructions et du site. A._ et B._ ont recouru auprès du Département cantonal des institutions et des relations extérieures (actuellement et ci-après: le Département de l'intérieur), qui a admis leur recours. Par arrêt du 23 décembre 2005, le Tribunal cantonal a annulé la décision précitée et renvoyé la cause au Département de l'intérieur pour qu'il statue à nouveau. Le 12 avril 2007, le Département de l'intérieur a admis le recours formé par A._ et B._ contre la décision de classement du 20 mars 2002. Il a considéré que, même si la notion de patrimoine était à prendre au sens large, la législation en matière de protection des monuments et des sites n'avait pas pour objectif de protéger des ambiances ou des atmosphères, tel l'esprit d'un village de pêcheurs. Au surplus, les mesures d'aménagement du territoire par le biais de la planification communale étaient plus efficaces et pertinentes dans le cas particulier. La Municipalité de St-Sulpice ainsi que les propriétaires des cabanons ont recouru au Tribunal cantonal contre cette décision (référence AC.2007.0103). E. Parallèlement à la procédure cantonale de classement, la commune de St-Sulpice a élaboré un plan partiel d'affectation "Aux Pierrettes - Les Champs du Lac", adopté par le Conseil communal le 18 septembre 2002. Celui-ci inclut notamment les parcelles 557 et 564, colloquées dans l'aire "des cabanons". Selon l'art. 2.2 du règlement du plan partiel d'affectation, cette aire a un statut de site protégé. Cette disposition a la teneur suivante : "Surface correspondant aux terrains sur lesquels sont implantées des petites constructions, témoignage d'un ancien village de pêcheurs. Cette petite entité bâtie a un statut de site protégé, tant en ce qui concerne la destination des constructions que leurs caractéristiques architecturales et la nature de leurs prolongements. Les constructions actuelles doivent être conservées et entretenues. Elles peuvent être modifiées et même reconstruites si des raisons objectivement fondées l'imposent. Lors de constructions nouvelles ou lors de transformations d'ouvrages existants, les travaux réalisés doivent respecter la nature du lieu et le caractère prédominant des constructions existantes, notamment leur forme, les matériaux utilisés et leurs aménagements extérieurs. La municipalité et le Service cantonal des bâtiments, section monuments historiques, sont habilités à imposer toute mesure propre à atteindre ces objectifs. Les petites constructions type "cabanon" ne comprennent qu'un seul niveau (rez-de-chaussée). Leur destination est en relation directe avec l'usage du port de petite batellerie (pêche, navigation de plaisance), par exemple: dépôt de matériel, locaux de service, lieux de détente." Quant à la parcelle 556, elle a été colloquée en aire de constructions, avec une possibilité de surface à bâtir allant jusqu'à 25 % de la superficie totale de la parcelle (art. 3.1 du règlement). La possibilité de bâtir a ainsi été augmentée de façon importante par rapport à celle autorisée dans la réglementation en vigueur, d'après laquelle la surface à bâtir de ladite parcelle ne pourrait excéder 1/10ème, soit 10 %, de la surface totale (cf. art. 28 du règlement communal du 12 septembre 1990 sur le plan d'affectation et la police des constructions). Par décision du 12 avril 2007, le Département de l'intérieur a rejeté le recours de A._ et B._ contre le plan partiel d'affectation du 18 septembre 2002. Il a estimé que l'absence de pêcheurs occupant les cabanons n'enlevait pas aux constructions la caractéristique que le plan d'affectation entendait protéger. La balance des intérêts avait en outre été correctement effectuée, puisqu'il ressortait du rapport X._ que la protection envisagée par le plan partiel d'affectation était fondée et que les atteintes à la parcelles 557 étaient largement compensées par les droits accordés sur la parcelle 556. A._ et B._ ont déféré cette décision au Tribunal cantonal (référence AC.2007.0107). F. Le 23 mai 2007, le Tribunal cantonal a joint les causes AC.2007.0103 et AC.2007.0107, considérant que la question du classement était liée à celle de l'affectation. Le 19 septembre 2008, le Tribunal cantonal a procédé à une vision locale en présence des parties. Par arrêt du 4 novembre 2008, il a admis les recours de C._ et consorts et de la Municipalité de St-Sulpice contre la décision relative à l'arrêté de classement; il a annulé la décision du Département de l'intérieur du 12 avril 2007 et confirmé la décision cantonale de classement du 22 mars 2002 classant le site du Port des Pierrettes (ch. I. du dispositif). Par ailleurs, il a très partiellement admis le recours de A._ et B._ et réformé la décision d'approbation préalable du Département de l'intérieur du 12 avril 2007 concernant le plan communal d'affectation "Aux Pierrettes - Les Champs du Lac" en ce sens que l'art. 2.2 du règlement est modifié de la manière suivante: "Art. 2.2 Al. 1: inchangé. Al. 2: Les constructions actuelles peuvent être reconstruites, en cas de nécessité ou en cas de destruction accidentelle, dans les gabarits existants au moment du classement et dans les limites fixées par la décision de classement. Al. 3: supprimé." (ch. II. du dispositif) Le Tribunal cantonal a considéré pour l'essentiel qu'il existait un intérêt public à la préservation du site et que les mesures litigieuses respectaient le principe de la proportionnalité et ménageaient l'atteinte aux intérêts privés de A._ et B._. G. Agissant par la voie du "recours de droit public", A._ et B._ demandent au Tribunal fédéral d'annuler l'arrêt du Tribunal cantonal du 4 novembre 2008. Subsidiairement, ils concluent à ce que le chiffre I du dispositif de l'arrêt attaqué soit réformé en ce sens que «l'art. 2 al. 1 de la décision de classement est modifié et a la teneur suivante: "Le classement s'étend au port traditionnel des Pierrettes. Il a pour but de protéger les site du port" et en ce sens que l'art. 2 al. 3 est supprimé, le plan annexé à la décision étant modifié en conséquence, le périmètre excluant la parcelle 557, et, cas échéant, la parcelle 564». A titre subsidiaire également, ils demandent la réforme du chiffre II du dispositif de l'arrêt attaqué en ce sens que l'art. 2.2 du règlement du plan partiel d'affectation "Aux Pierrettes - Les Champs du Lac" est biffé et l'aire des cabanons supprimée du plan. En outre, ils concluent à ce que des dépens de première instance fixés à 6'000 fr. leur soient alloués, à la charge de la Municipalité de St-Sulpice, de C._ et consorts ainsi que de l'Etat de Vaud. Le Tribunal cantonal a renoncé à déposer une réponse et se réfère aux considérants de son arrêt. La commune de St-Sulpice et le Département des infrastructures concluent au rejet du recours. C._ et consorts concluent également au rejet du recours, dans la mesure où il est recevable. Par ordonnance du 19 janvier 2009, le Président de la Ire Cour de droit public a rejeté la requête d'effet suspensif contenue dans le recours.