Faits: A. Le 30 mai 2011, le Conseil municipal de E._ a accordé des permis de construire pour douze immeubles d'habitation aux requérants "Z._". B.X._ et A.X._, ainsi que D.Y._ et C.Y._ ont recouru avec succès contre cette décision auprès du Conseil d'Etat valaisan. Celui-ci a ordonné à Z._ SA de verser une indemnité de 1'500 fr. à titre de dépens aux quatre recourants, créanciers solidaires (ch. 6 du dispositif de la décision du 24 octobre 2012). B. Par mémoire du 29 novembre 2012, B.X._, A.X._, D.Y._ et C.Y._ ont interjeté recours contre cette décision, requérant l'annulation du chiffre 6 de son dispositif, la fixation de l'indemnité de dépens par le Tribunal cantonal et, à titre subsidiaire, le renvoi de la cause sur cette question à l'autorité précédente. Ils ont produit la liste de frais de leur conseil, qui s'élevait pour la période de décembre 2009 à fin octobre 2012 à 7'953 fr. Le 29 mai 2013, le Tribunal cantonal valaisan a rejeté ce recours. C. Par acte du 27 juin 2013, B.X._ et A.X._, ainsi que D.Y._ et C.Y._ forment recours contre cette décision, concluant à son annulation. Ils demandent que le Tribunal fédéral fixe l'indemnité de dépens et, subsidiairement, que la cause soit renvoyée au Tribunal cantonal pour nouvelle décision. Invitée à se déterminer, Z._ SA, par le biais de son mandataire, n'a pas désiré se prononcer ou être partie dans la procédure fédérale. Elle a relevé qu'elle ignorait comment elle avait été impliquée dans cette cause, affirmant notamment n'être pas la destinataire des décisions rendues dans celle-ci. Quant au Conseil d'Etat valaisan, il a conclu au rejet du recours dans la mesure de sa recevabilité. Le Tribunal cantonal a renoncé à se déterminer. Les recourants n'ont pas déposé d'observations complémentaires. 