Faits: A. Le 29 mars 2007, le Service de l'économie, du logement et du tourisme du canton de Vaud (ci-après: le Service de l'économie) a accordé une licence provisoire de tea-room pour l'établissement A._, à B._, qui comprenait l'autorisation d'exploiter l'établissement au nom de la société Y._ SA, à Zurich, et l'autorisation d'exercer au nom de X._, à Genève. La validité de cette licence était fixée du 1er avril au 31 juillet 2007, dans l'attente de la réussite de ce dernier à l'examen professionnel en vue de l'obtention du certificat de capacité de la catégorie d'établissement concernée. Une prolongation au 30 avril 2008 a été accordée par l'octroi, le 8 février 2008, d'une deuxième licence provisoire. La licence d'établissement no LADB-EV-2008-**** a finalement été délivrée le 9 juin 2008, pour une durée de quatre ans, soit jusqu'au 30 avril 2012. B. Dans un rapport du 3 juin 2008 adressé à X._ et en copie à Y._ SA, l'inspecteur du Service de l'emploi qui, les 28 février et 4 avril 2008, avait procédé à deux contrôles de l'établissement A._ a constaté que les conditions de travail et la gestion du personnel n'étaient pas conformes aux prescriptions légales et conventionnelles sur plusieurs points: absence de planning des horaires de l'établissement du titulaire de l'autorisation d'exercer, dossiers du personnel incomplets, horaires effectifs non quittancés, compensation des heures supplémentaires et pauses repas invérifiables, nombre d'heures de travail et de repos non respecté, travail de nuit non compensé, salaire minimum pas respecté, jours fériés payés à 1,66% du salaire au lieu de 2,27%, salaire en nature non déclaré, emploi à plusieurs reprises d'un mineur après 22 heures. Un délai de deux mois était fixé aux intéressés pour remédier aux irrégularités constatées (points du rapport marqués en rouge). Par courrier du 1er septembre 2008, le Service de l'économie, constatant qu'aucune preuve écrite de la régularisation de la situation de l'établissement n'avait été fournie, a invité X._ à se présenter, le 15 septembre 2008, en possession de toutes les pièces propres à apporter cette preuve. Le 9 septembre 2008, il a adressé la même convocation à la société Y._ SA. E._, représentant de Y._ SA, s'est présenté seul à la séance du 15 septembre 2008. Il a notamment produit les horaires des employés de janvier et février 2008, ainsi que le "payroll" des employés de décembre 2007 à février 2008. Par décision du 24 septembre 2008, le Service de l'économie a ordonné, avec effet immédiat et sous commination de la peine prévue à l'art. 292 CP, le retrait de l'autorisation d'exercer de X._ et de l'autorisation d'exploiter de Y._ SA pour le tea-room A._, à B._, ainsi que la fermeture de cet établissement et le retrait de la licence no LADB-EV_2008-****. Le Service de l'économie a considéré que les pièces produites le 15 septembre 2008 ne démontraient pas une régularisation de la situation et que les manquements relevés par le Service de l'emploi dans les conditions de travail et la gestion du personnel constituaient des violations graves et répétées du droit du travail. En outre, il a retenu que, contacté par téléphone le 15 septembre 2008, X._ avait admis travailler à plein temps dans un autre établissement de la chaîne A._, à Lausanne, et mettre à disposition de Y._ SA son certificat de capacité. Or, l'utilisation d'un prête-nom à seul fin de bénéficier d'une autorisation d'exercer pour obtenir la licence d'établissement constituait une violation grave des dispositions de la législation cantonale sur les auberges et les débits de boissons. C. X._ et Y._ SA ont recouru contre cette décision auprès du Tribunal cantonal vaudois (Cour de droit administratif et public). Ils ont notamment demandé à être entendus et requis l'audition de témoins. Le 8 décembre 2008, les recourants se sont vus impartir un délai pour produire les documents démontrant que leur situation avait été régularisée et établir que X._ exerçait bien son activité dans l'établissement de B._ et non pas à Lausanne. Le 8 janvier 2009, ils ont communiqué de nouvelles pièces. Statuant le 30 mars 2009 , le Tribunal cantonal a rejeté le recours. D. X._ et la société Y._ SA forment un recours en matière de droit public auprès du Tribunal fédéral et concluent, avec suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 30 mars 2009, subsidiairement à l'annulation dudit arrêt et au renvoi de la cause à l'autorité cantonale pour nouvelle instruction et nouvelle décision. Les recourants ont également présenté une demande d'effet suspensif, qui a été admise, par ordonnance présidentielle du 11 juin 2009. Le Tribunal cantonal se réfère aux considérants de son arrêt et conclut au rejet du recours. Au terme de ses déterminations, le Service de l'économie conclut au rejet du recours pour autant qu'il soit recevable, avec suite de frais. 