Faits: A. Par avis publié au Bulletin officiel du 27 novembre 2009, la commune de Monthey a mis à l'enquête publique le réaménagement des rues du Fay, du Théâtre, du Marquisat et de l'avenue de la Gare, la réalisation d'un pont sur la Vièze en prolongement de la rue du Marquisat ainsi que la création d'un giratoire sur l'avenue du Simplon. Le dossier déposé contenait entre autres un plan de signalisation traduisant la nouvelle gestion du trafic que la commune entendait introduire dans le centre-ville ainsi qu'une expertise sur les zones 30 et de rencontre. Ce projet, dit de la Petite Ceinture, découle du plan directeur des espaces publics du centre-ville de Monthey (ci-après: le plan directeur), élaboré en novembre 2005. Adopté par le Conseil communal le 23 janvier 2006, cet instrument propose une stratégie d'intervention dans le centre-ville, dont l'un des axes consiste à déplacer la circulation nord-sud - qui s'écoule actuellement en sens unique sur les avenues du Crochetan, du Midi et l'avenue de Venise - sur une large avenue reprenant, en double sens, le tracé actuel des rues du Fay, du Théâtre, de la Tannerie et du Marquisat, plus à l'est. Un pont à créer sur la Vièze doit permettre le raccord de cette artère à l'avenue du Simplon. La commune se propose de modérer le trafic sur ce nouvel axe en limitant la vitesse à 30 km/h sur la rue du Marquisat, puis de créer une zone de rencontre s'étendant sur les rues de la Tannerie, du Théâtre et du Fay. La publication au Bulletin officiel a suscité plusieurs oppositions, dont celles de B._ et A._. Le 29 juillet 2010, la commune a transmis le dossier au Département cantonal des transports, de l'équipement et de l'environnement, en proposant d'écarter les oppositions, d'approuver le projet de réaménagement routier et de déclarer les travaux d'intérêt public. B. Le 7 décembre 2010, le Conseil d'Etat a approuvé les plans routiers et a autorisé les expropriations induites par le projet. Il a rejeté simultanément les oppositions. Par arrêt du 26 août 2011, le Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours de B._ et A._ dans la mesure où il était recevable. Il a considéré en substance que la procédure suivie n'était pas critiquable et que l'instauration des zones 30 et de rencontre sur les voies publiques concernées par le projet était conforme au droit. C. Agissant par la voie du recours en matière de droit public, B._ et A._ demandent au Tribunal fédéral d'annuler la décision du Tribunal cantonal du 26 août 2011 et de rejeter le projet soumis à l'enquête publique le 27 novembre 2009. Ils se plaignent de vices de procédure ainsi que d'une violation du droit fédéral relatif à la circulation routière. Le Tribunal cantonal renonce à se déterminer sur le recours. Le Département cantonal des transports, de l'équipement et de l'environnement conclut au rejet du recours. La commune de Monthey conclut également au rejet du recours, dans la mesure de sa recevabilité, et à la confirmation du projet de réaménagement routier approuvé par le Conseil d'Etat le 7 décembre 2011. Les recourants ont répliqué le 20 janvier 2012; ils confirment les conclusions prises dans leur recours.