Faits: A. Y._ est associé gérant de la société à responsabilité limitée X._ Sàrl (ci-après: la recourante), sise à Neuchâtel, dont le but est en premier lieu l'exploitation d'une agence privée de sécurité. Le 26 juillet 1999, une autorisation d'exploiter une entreprise de sécurité au sens du concordat du 18 octobre 1996 sur les entreprises de sécurité (RSN 568.10; ci-après: le concordat; voir aussi l'arrêté neuchâtelois d'exécution du concordat sur les entreprises de sécurité, du 14 décembre 1998 [RSN 568.100; ci-après: l'arrêté]) a été délivrée. Dans le courant de l'année 2005, la Police cantonale neuchâteloise a dû procéder d'office à la radiation du registre ad hoc de 9 agents de sécurité de X._ Sàrl, dont les cartes de légitimation étaient arrivées à échéance sans qu'aucune demande de renouvellement ou de radiation n'ait été présentée. Il a ainsi été retenu que Y._ avait violé le concordat en n'annonçant pas les départs de certains agents et en en employant d'autres alors que leurs autorisations concordataires n'étaient plus valables. Afin de sanctionner ces manquements, la Police cantonale a, en date du 9 août 2006, adressé à Y._ un avertissement formel. A cette occasion, il lui a été signifié qu'une procédure de retrait d'autorisation serait engagée si de nouvelles infractions au concordat et à l'arrêté étaient constatées dans les deux ans. Lors d'un contrôle effectué le 18 août 2006, la Police cantonale a relevé que le personnel de X._ Sàrl ne bénéficiait d'aucune formation (initiale ou continue) depuis le 1er juillet 2005, cela en violation du concordat et de l'arrêté. Au vu de l'avertissement formel récemment prononcé, seul un avertissement verbal a été adressé à Y._. Dénoncé pour ces faits sur le plan pénal, Y._ s'est vu infliger une amende de 2'500 fr. pour avoir contrevenu aux art. 11 al. 1 et 15a du concordat. Entre janvier et février 2007, la Police cantonale a dû, une nouvelle fois, procéder à la radiation de 3 agents ?uvrant pour X._ Sàrl, dont les cartes concordataires étaient arrivées à échéance sans qu'aucune demande de renouvellement ou de radiation n'ait été présentée. En raison de ces faits, un deuxième avertissement formel a été adressé à Y._ en date du 8 mai 2007. Lors d'un contrôle du 16 avril 2008, la Police cantonale a constaté que la majorité des agents de sécurité employés par X._ Sàrl n'avaient pas suivi les cours de formation requis. B. Par décision du 1er juillet 2008, la Police cantonale a suspendu provisoirement l'autorisation d'exploiter l'entreprise de sécurité X._ Sàrl pour une durée de deux mois. Elle a enjoint à Y._ d'entreprendre durant ce délai toutes les démarches en vue de remédier aux manquements constatés et d'assurer une formation adéquate à son personnel et l'a averti qu'en cas de non-respect de ces obligations, une sanction plus sévère serait prononcée. L'autorité a considéré que les manquements constatés au niveau de la formation du personnel constituaient une violation grave des règles régissant l'activité des entreprises de sécurité. Elle a également relevé que les dysfonctionnements de l'entreprise mettaient en évidence une certaine négligence dans la conduite de celle-ci, Y._ persistant, en dépit de deux avertissements, à invoquer des problèmes de restructuration pour justifier son comportement. Compte tenu du nombre d'irrégularités constatées dans la gestion de X._ Sàrl et du manque de réaction de l'intéressé pour y remédier, l'autorité a estimé que seule une suspension de deux mois de l'autorisation d'exploiter entrait en considération. Le 21 juillet 2008, X._ Sàrl et Y._ ont interjeté recours contre ce prononcé auprès du Département de la justice, de la sécurité et des finances du canton de Neuchâtel (ci-après: le Département cantonal), qui les déboutés par décision du 10 août 2010. Le recours interjeté contre cette décision auprès du Tribunal administratif - devenu entre-temps la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal) - a été rejeté par arrêt du 15 mars 2012. C. Contre cet arrêt, X._ Sàrl et Y._ forment un "recours de droit public" auprès du Tribunal fédéral. Ils concluent, sous suite de frais et dépens, à l'annulation du jugement attaqué et au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Le Tribunal cantonal, le Département cantonal et la Police cantonale concluent au rejet du recours, sous suite de frais. 