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.

Considérant en droit:
1. Dirigé contre une décision rendue dans le domaine du droit public des constructions, le recours est recevable comme recours en matière de droit public conformément aux <ref-law>, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. Les recourants ont pris part à la procédure de recours devant le Tribunal cantonal et sont particulièrement touchés par l'arrêt attaqué, qui confirme l'ordre de remise en état de leur couvert à voitures. Ils ont donc la qualité pour agir au sens de l'<ref-law>. Pour le surplus, interjeté en temps utile et dans les formes requises 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 au regard des art. 42, 86 al. 1 let. d, 90 et 100 al. 1 LTF.
2. Les recourants se plaignent d'une atteinte à la garantie de la propriété (art. 26 Cst.), d'une application arbitraire de la directive AEAI et d'une violation du principe de la proportionnalité. Ils invoquent également l'art. 22 LAT, sans toutefois développer d'argumentation à cet égard, de sorte qu'il n'y a pas lieu d'examiner l'application de cette dernière disposition (<ref-law>).
2.1 Comme tout droit fondamental, la propriété ne peut être restreinte qu'aux conditions de l'art. 36 Cst. La restriction doit donc reposer sur une base légale - respectivement sur une loi au sens formel si la restriction est grave - (al. 1), être justifiée par un intérêt public (al. 2) et respecter le principe de la proportionnalité (al. 3). Le principe de la proportionnalité exige que le moyen choisi soit apte à atteindre le but visé (règle de l'aptitude) et que celui-ci ne puisse pas être atteint par une mesure moins incisive (règle de la nécessité); en outre, il interdit toute limitation allant au-delà du but visé et il exige un rapport raisonnable entre celui-ci et les intérêts publics ou privés compromis (principe de la proportionnalité au sens étroit, impliquant une pesée des intérêts - <ref-ruling> consid. 7.2 p. 62; <ref-ruling> consid. 5.2 p. 438; <ref-ruling> consid. 2c p. 222 et les arrêts cités).
2.2 L'atteinte au droit de propriété est considérée comme particulièrement grave lorsque la propriété foncière est enlevée de force ou lorsque des interdictions ou des prescriptions positives rendent impossible ou beaucoup plus difficile une utilisation du sol - actuelle ou future - conforme à sa destination (<ref-ruling> consid. 2 p. 190). En revanche, n'ont pas été considérées comme des restrictions graves à la propriété les décisions qui refusent une autorisation de construire au motif que l'indice d'utilisation du sol est dépassé (arrêt 1C_332/2007 du 13 mars 2008, consid. 2.2 et les arrêts cités), la décision qui impose de suivre les règles d'une zone réservée à des "activités sans nuisances" (arrêt 1A.9/2005 du 4 août 2005 consid. 4.1) ou encore l'obligation d'installer une clôture autour d'un étang de 30 m sur 15 m (arrêt 1P.837/2005 du 31 janvier 2006, consid. 2.1).
En l'espèce, la décision de mise en conformité tend au remplacement des bardeaux du couvert à voitures par des ardoises. Elle porte certes atteinte à la propriété des recourants, mais elle ne constitue pas une restriction grave au sens de la jurisprudence précitée. Par conséquent, le Tribunal fédéral n'examine que sous l'angle de l'arbitraire la question de la base légale ainsi que l'interprétation et l'application du droit cantonal (<ref-ruling> consid. 14.2 p. 362; <ref-ruling> consid. 2.2 p. 177; <ref-ruling> consid. 3a p. 218). Il examine en revanche librement les questions de l'intérêt public et de la proportionnalité, en s'imposant toutefois une certaine réserve lorsqu'il s'agit de tenir compte de circonstances locales ou de trancher de pures questions d'appréciation (<ref-ruling> consid. 4.3 p. 416; <ref-ruling> consid. 4.1 p. 344; <ref-ruling> consid. 3a p. 366).
3. En critiquant l'absence de base légale pour leur interdire la pose de bardeaux sur leur couvert, les recourants perdent de vue que la décision litigieuse n'est pas un refus d'autorisation de construire mais bien un ordre de remise en état au sens de l'art. 51 al. 1 et 2 LC. Cette disposition prévoit notamment que la remise en état est ordonnée lorsqu'un projet est exécuté contrairement à l'autorisation délivrée. Or, la construction réalisée en l'espèce n'est pas conforme au permis de construire, qui comportait la condition suivante (n. 17): "le matériau de couverture sera de couleur anthracite (ardoises du pays)". Cette condition est d'ailleurs conforme à la demande d'autorisation de construire déposée par les recourants, dans laquelle ils annonçaient que la couverture serait réalisée en "ardoises naturelles du pays". Dans ces conditions, l'art. 51 LC constitue déjà une base légale suffisante pour justifier l'atteinte à la propriété découlant de l'ordre de remise en état.
Au demeurant, la décision litigieuse se fonde encore sur d'autres normes. L'art. 27 al. 1 LC prescrit en effet que les constructions doivent être conformes aux exigences en matière de police du feu. Selon l'art. 6 al. 3 de la loi cantonale du 18 novembre 1977 sur la protection contre l'incendie et les éléments naturels (LPI; RS/VS 540.1), le Conseil d'Etat arrête les prescriptions techniques applicables pour la prévention contre les incendies, ce que cette autorité a fait en adoptant l'ordonnance du 12 décembre 2001 concernant les mesures préventives contre les incendies (RS/VS 540.102). L'art. 1 al. 2 de cette ordonnance renvoie à son annexe pour la liste des prescriptions techniques applicables, parmi lesquelles figurent la norme et la directive AEAI. Enfin, selon l'arrêt attaqué, l'art. 71 let. a RCC prévoit que la couverture doit être réalisée en "ardoises naturelles ou artificielles". Dans la mesure où l'atteinte à la propriété des recourants ne peut pas être qualifiée de grave, l'ensemble de ces normes constitue une base légale suffisante, que le Tribunal fédéral examine uniquement sous l'angle de l'arbitraire.
4. En l'occurrence, seule l'application de l'art. 8.1 de la directive AEIA est critiquée par les recourants sous l'angle de l'arbitraire.
4.1 Selon la jurisprudence, l'arbitraire, prohibé par l'art. 9 Cst., ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral ne s'écarte de la solution retenue en dernière instance cantonale que si elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté ou si elle heurte de manière choquante le sentiment de la justice ou de l'équité. Il ne suffit pas que la motivation de la décision soit insoutenable; encore faut-il qu'elle soit arbitraire dans son résultat (<ref-ruling> consid. 3.1 p. 153; <ref-ruling> consid. 5.1 p. 17; <ref-ruling> consid. 2.1 p. 219; <ref-ruling> consid. 3.1 p. 178).
4.2 Applicable en vertu des art. 27 al. 1 LC, 6 al. 3 LPI et 1 al. 2 de l'ordonnance du 12 décembre 2001 concernant les mesures préventives contre les incendies, l'art. 8.1 de la directive AEIA a la teneur suivante:
1Les matériaux et le mode de construction des toitures ne doivent pas favoriser la propagation des incendies de niveau en niveau, ni mettre en danger le voisinage.
2La couche supérieure des toitures doit être incombustible; les exceptions dépendent du type de construction et de l'importance de la surface de toiture. Ceci est également valable pour les couches d'isolation thermique et les autres couches des toits.
[...]
4.3 Conformément à cette disposition, l'exigence selon laquelle la couche supérieure des toitures doit être incombustible constitue la règle. Cela étant, comme le relèvent les recourants, il est exact que l'alinéa 2 réserve des exceptions. Le Tribunal cantonal a toutefois considéré qu'il n'y avait pas lieu de faire une telle exception dans le cas d'espèce. Il a souligné qu'une couverture en bois n'était pas imposée par les circonstances, s'agissant d'une construction entièrement neuve réalisée dans une zone où le RCC prescrit expressément une couverture en ardoises. De plus, compte tenu de ses dimensions (93 m2), le couvert litigieux ne pouvait pas être considéré comme une construction de peu d'importance sous l'angle du risque de propagation du feu ou du danger pour le voisinage. Le fait que les règles sur les distances latérales soient différentes pour un couvert et pour une construction destinée à abriter des personnes n'y changeait rien, les règles sur les distances et sur les matériaux étant cumulatives sous l'angle de la prévention de la propagation du feu.
Contrairement à ce que soutiennent les recourants, le Tribunal cantonal n'a pas totalement fait abstraction du fait que leur construction était destinée à abriter des véhicules automobiles et non des personnes et qu'il répondait dès lors à des exigences différentes quant aux distances de sécurité. Il a au contraire examiné cet argument dans le cadre d'une appréciation globale de la construction litigieuse sous l'angle des risques de propagation du feu, ce qui n'apparaît pas en soi comme manifestement insoutenable. Pour le surplus, la motivation de l'arrêt attaqué selon laquelle les circonstances ne justifiaient pas de faire une exception pour le couvert litigieux apparaît objectivement fondée et les recourants ne démontrent pas en quoi elle serait arbitraire au sens de la jurisprudence susmentionnée. Ce moyen doit donc être rejeté.
5. Il reste à examiner si l'ordre de remise en état viole le principe de la proportionnalité, comme le soutiennent les recourants.
5.1 Selon la jurisprudence, l'autorité renonce à ordonner la remise en état 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 (<ref-ruling> consid. 3bb p. 252; <ref-ruling> consid. 6b p. 224s.; <ref-ruling> consid. 4 p. 69). Même un constructeur qui n'est pas de bonne foi peut invoquer le principe de proportionnalité. Toutefois, celui qui place l'autorité devant un fait accompli doit 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. 4a p. 255; <ref-ruling> consid. 6b p. 224 et la jurisprudence citée).
5.2 En l'espèce, l'irrégularité ne saurait être qualifiée de mineure, le couvert à voitures étant entièrement recouvert d'un matériau combustible, contrairement à ce que prévoient le permis de construire et les prescriptions relatives à la protection contre les incendies. Il n'y a dès lors pas de chances sérieuses de faire reconnaître la construction comme conforme au droit. Citant un courrier dans lequel leur architecte rapporte les propos d'un responsable du service du feu communal, les recourants semblent soutenir qu'ils ont obtenu des garanties que la couverture en bardeaux serait autorisée. A cet égard, le Tribunal cantonal relève à juste titre que les supposées déclarations d'un employé municipal - au demeurant contestées par la commune en cause - ne sauraient prévaloir sur le permis de construire et engager le conseil communal. De plus, dans la mesure où les recourants étaient représentés par un professionnel de la construction, ils ne pouvaient ignorer que seule cette autorité était compétente pour statuer sur ce point. Ils ne sauraient dès lors se prévaloir de leur bonne foi.
Par ailleurs, la décision litigieuse est motivée par un intérêt public évident lié au respect des autorisations de construire ainsi que par un souci de minimiser les risques de propagation des incendies. Au regard de cet intérêt public, les considérations des recourants sur l'esthétique des bardeaux et l'absence de plainte des propriétaires voisins sont sans pertinence. Il en va de même de l'existence d'autres toitures de bardeaux à Verbier, les recourants ne se plaignant pas d'une violation de l'égalité de traitement au sens de l'art. 8 Cst. Pour le surplus, les recourants se bornent à minimiser l'irrégularité de leur construction mais ils ne se prévalent pas d'un intérêt privé qui devrait l'emporter sur les intérêt publics précités. Il y a donc lieu de constater que le principe de la proportionnalité est respecté.
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é. La décision de la Commune de Bagnes du 9 mai 2006 - notifiée le 4 juillet 2007 - est confirmée, un nouveau délai de six mois dès la notification du présent arrêt étant imparti à A._ et B._ pour effectuer les travaux de remise en état des lieux.
2. Les frais judiciaires, arrêtés à 3000 fr., sont mis à la charge de A._ et B._.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué au mandataire des recourants, à la Commune de Bagnes et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 21 janvier 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener