Faits: A. A._ et sa soeur B._ sont propriétaires de la parcelle n° 4777 du registre foncier de Bagnes (VS). Le 15 juin 2005, ils ont requis l'autorisation de construire sur ce bien-fonds un couvert pour six voitures. Selon les plans déposés, cette construction aurait une longueur de 17,20 m, une largeur de 5,40 m et une hauteur de 4 m au faîte. La formule de demande d'autorisation précisait que la toiture du couvert serait réalisée en "ardoises naturelles du pays", conformément aux exigences du règlement de construction de Verbier-station du 14 juin 1996, approuvé par le Conseil d'Etat du canton du Valais le 16 septembre 1998 (ci-après: le RCC). Mis à l'enquête publique sans susciter d'opposition, le projet a été autorisé le 11 novembre 2005 par le Conseil communal de Bagnes. Les conditions et charges de l'autorisation de construire rappelaient que la toiture devrait être recouverte par un matériau "de couleur anthracite (ardoises du pays)". Durant les travaux, les constructeurs ont décidé de couvrir le toit avec des bardeaux au lieu des ardoises initialement prévues. Ils alléguaient avoir obtenu pour ce faire l'accord oral du responsable du Service communal du feu, ce qui est contesté par la Commune de Bagnes. Par décision du 9 mai 2006, notifiée le 4 juillet 2007, le conseil communal a ordonné à A._ et B._ de mettre leur couvert en conformité avec l'autorisation de construire. Constatant que la construction litigieuse était contraire au RCC et qu'elle ne respectait pas les dispositions légales de protection contre les incendies imposées par la loi cantonale du 8 février 1996 sur les constructions (LC; RS/VS 705.1), le conseil communal a sommé les prénommés de démolir la couverture en bardeaux et de la remplacer par des ardoises naturelles dans un délai de six mois. B. A._ et B._ ont contesté cette décision devant le Conseil d'Etat. Cette autorité a rejeté le recours par décision du 5 décembre 2007, estimant notamment que le conseil communal avait appliqué correctement la norme et la directive de l'Association des établissements cantonaux d'assurance incendie éditées en 2003 (ci-après: la norme et la directive AEAI), qui prévoient que la couche supérieure des toitures doit être incombustible (art. 8.1 al. 2 de la directive AEAI). A._ et B._ ont recouru contre cette décision auprès du Tribunal cantonal du canton du Valais, Cour de droit public (ci-après: le Tribunal cantonal), qui a rejeté le recours par arrêt du 4 juillet 2008. Le Tribunal cantonal a considéré en substance que la règle générale de l'art. 8.1 al. 2 de la directive AEAI s'appliquait au couvert litigieux et qu'il n'y avait aucune circonstance permettant d'y déroger. De plus, l'ordre de remise en état respectait le principe de la proportionnalité, l'intérêt public lié à la protection contre la propagation des incendies l'emportant sur l'intérêt privé des propriétaires du couvert à voitures. 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 invoquent une violation de l'art. 22 LAT ainsi que du principe de la proportionnalité (art. 5 al. 2 Cst.) et de la garantie de la propriété (art. 26 Cst.). Ils se plaignent également d'une application arbitraire (art. 9 Cst.) de la directive AEAI. Ils requièrent en outre l'octroi de l'effet suspensif. Le Tribunal cantonal et la Commune de Bagnes ont renoncé à se déterminer. D. Par ordonnance du 2 octobre 2008, le Président de la Ire Cour de droit public a accordé l'effet suspensif au recours.