Faits: A. X._ est propriétaire de quatre bien-fonds de la commune de Conthey, classés en zone de mayens par le plan d'affectation communal approuvé le 10 juin 1997 par le Conseil d'Etat du canton du Valais. Au mois de février 2004, le propriétaire a reçu l'autorisation d'y transformer et agrandir un mayen où il vit durant toute l'année avec sa famille; les abords immédiats de ce bâtiment sont aménagés en pelouses, terrasses et accès pour véhicules. Dès le 20 mars 2008, le propriétaire est entré en pourparlers avec l'autorité communale afin d'obtenir l'autorisation de construire une remise a proximité du mayen. Se référant au règlement applicable, l'autorité envisageait d'autoriser une modeste remise qui n'excéderait pas 15 m3, ce que le propriétaire tenait pour insuffisant au regard de ses besoins. L'autorité n'était pas disposée à accorder une dérogation. En définitive, le 7 décembre 2009, elle a autorisé une remise carrée de 2m50 de côté, haute de 2m40 au faîte, totalisant 13 m3 75; la demande correspondante avait été publiée et elle n'avait pas suscité d'opposition. B. Le 23 février 2010, la police municipale a constaté la présence d'une remise en bois style « chalet », de 4m54 par 3m05, pourvue d'un couvert long de 3m64. Le 11 mars suivant, l'autorité communale a ordonné la modification de cet ouvrage afin de le rendre conforme à l'autorisation de construire déjà délivrée; le propriétaire pouvait toutefois introduire une nouvelle demande destinée à régulariser le bâtiment existant. X._ a présenté une nouvelle demande le 9 avril 2010; il a fait valoir que l'ordre de remise en état ne répondait à aucun intérêt public et qu'une dérogation se justifiait en considération des besoins d'une habitation occupée durant toute l'année et des nécessités d'une activité viticole annexe. Il a également fait valoir que le territoire communal comportait de nombreuses constructions illégales. Le 19 mai 2010, l'autorité communale a confirmé l'ordre de remise en état et elle a assigné au propriétaire un nouveau délai d'exécution. Elle considérait que les couverts et autres installations fixes sont interdits en zone de mayens et que celle-ci n'est destinée ni à l'habitation permanente ni au dépôt de matériel viticole. X._ ayant recouru au Conseil d'Etat, la commune a admis qu'elle aurait dû se prononcer formellement sur la demande de régularisation présentée le 9 avril 2010. Elle l'a fait par décision du 22 septembre 2010; elle a alors confirmé l'ordre de remise en état. X._ a derechef saisi le Conseil d'Etat, lequel a rejeté le recours le 28 septembre 2011. La Cour de droit public du Tribunal cantonal a rejeté le recours ultérieur du propriétaire le 30 mars 2012. C. Agissant par la voie du recours en matière de droit public, X._ requiert le Tribunal fédéral de réformer l'arrêt du Tribunal cantonal en ce sens que la demande de régularisation introduite le 9 avril 2010 soit accueillie. A titre subsidiaire, le recourant demande d'être autorisé à conserver la remise existante, sans le couvert. La commune de Conthey a conclu au rejet du recours; les autorités cantonales ont renoncé à présenter des observations. Invité à prendre position, l'Office fédéral du développement territorial propose au Tribunal fédéral de déclarer les autorités communales incompétentes au motif que la construction se trouve hors de la zone à bâtir; pour le surplus, il propose « au minimum » la confirmation de l'ordre de remise en état. Ayant pris connaissance de cet avis, le recourant et la commune de Conthey ont persisté dans leurs conclusions respectives.