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.

Considérant en droit:
1. 1.1 La voie du recours en matière de droit public (<ref-law>) est en l'occurrence ouverte. Les conditions de recevabilité d'un tel recours étant réunies, il convient en principe d'entrer en matière.
1.2 Le recours peut être formé pour violation du droit fédéral (cf. <ref-law>), y compris le droit constitutionnel, ainsi du droit intercantonal (cf. art. 95 let. e LTF), dont fait partie le concordat. Le Tribunal fédéral n'examine que les griefs invoqués et motivés de façon détaillée par la partie recourante (<ref-law>).
2. Les recourants considèrent que la sanction infligée viole la liberté économique et les exposerait potentiellement à la faillite, eu égard au fait que, dans le domaine de la sécurité, les contrats sont généralement de longue durée. Ils ne contestent pas l'existence d'une base légale, ni les manquements mentionnés plus haut, ni le fait que la décision litigieuse a été précédée de deux avertissements, mais s'en prennent à la proportionnalité de la sanction.
2.1 Selon l'art. 27 al. 1 Cst., la liberté économique est garantie. Elle comprend notamment le libre choix de la profession, le libre accès à une activité économique lucrative privée et son libre exercice (art. 27 al. 2 Cst.). Cette liberté protège toute activité économique privée, exercée à titre professionnel et tendant à la production d'un gain ou d'un revenu (<ref-ruling> consid. 4c/aa p. 29). Conformément à l'art. 36 al. 1 Cst., toute restriction d'un droit fondamental doit être fondée sur une base légale, les restrictions graves devant être prévues par une loi. Une telle restriction doit en outre être justifiée par un intérêt public ou par la protection d'un droit fondamental d'autrui (art. 36 al. 2 Cst.) et être proportionnée au but visé (art. 36 al. 3 Cst.). S'agissant de l'intérêt public pouvant justifier une restriction à la liberté économique, la jurisprudence distingue entre les mesures de police, les mesures de politique sociale, ainsi que les mesures dictées par la réalisation d'autres intérêts publics. Les restrictions de police sont celles qui visent à protéger l'ordre public, c'est-à-dire la tranquillité, la sécurité, la santé ou la moralité publiques, ainsi que la bonne foi en affaires (<ref-ruling> consid. 3a p. 326 et les arrêts cités).
2.2 Comme le relève l'autorité précédente, en tant qu'elle empêche les recourants d'exploiter une entreprise de sécurité durant deux mois, la sanction prononcée constitue une atteinte grave à la liberté économique garantie par l'art. 27 Cst. Par conséquent, l'art. 36 Cst. exige qu'une telle restriction repose sur une base légale formelle, qu'elle soit justifiée par un intérêt public et qu'elle soit proportionnée au but visé, ce que le Tribunal de céans vérifie librement (<ref-ruling> consid. 4 p. 339 s.).
2.3 Les cantons de Fribourg, Vaud, Valais, Neuchâtel, Genève et Jura sont parties au concordat, dont les buts sont de fixer des règles communes régissant l'activité des entreprises de sécurité et de leurs agents et d'assurer la validité intercantonale des autorisations accordées par les cantons (art. 2 du concordat). Cette convention régit les activités de surveillance ou de garde de biens mobiliers ou immobiliers, de protection des personnes et de transport de sécurité de biens ou de valeurs, exercées à titre principal ou accessoire soit par du personnel, soit au moyen d'installations adéquates (art. 4 du concordat). Dans le canton de Neuchâtel, la Police cantonale est l'autorité compétente pour prendre les mesures administratives prévues par l'art. 13 du concordat (art. 2 al. 2 et art. 3 let. h de l'arrêté).
Le Tribunal cantonal a clairement exposé les dispositions concordataires fondant l'obligation d'obtenir une autorisation notamment pour exploiter une entreprise de sécurité et engager du personnel à cet effet. S'agissant des mesures administratives, l'autorité qui a accordé l'autorisation doit la retirer lorsque les conditions prévues aux articles 8, 9 et 10a ne sont plus remplies ou lorsque son titulaire contrevient gravement ou à de réitérées reprises aux dispositions du concordat ou de la législation cantonale d'application (art. 13 al. 1 du concordat). L'autorité peut également prononcer un avertissement ou une suspension de l'autorisation de un à six mois (art. 13 al. 3 du concordat). Le concordat ne prévoit ainsi pas l'amende au nombre des peines susceptibles de frapper un contrevenant à dite règlementation. Les différentes obligations relatives aux formations initiale et ultérieure des agents ont également été détaillées par la Cour cantonale et il peut à cet égard être renvoyé au jugement entrepris. S'agissant des buts visés par ces formations, il convient de reprendre les considérants topiques de l'arrêt attaqué, dès lors que ceux-ci permettent de juger de la proportionnalité de la mesure. Ainsi, au vu des tâches qui lui sont généralement confiées, il est important que l'agent de sécurité respecte la législation fédérale et cantonale, en particulier les dispositions réglant le recours à la force, la légitime défense et l'état de nécessité, qu'il n'entrave pas l'action des autorités et de la police, qu'il prête assistance à cette dernière en conformité avec les dispositions cantonales et qu'il dénonce sans délai à l'autorité pénale compétente tout fait pouvant constituer un crime ou un délit poursuivi d'office. Le personnel de sécurité doit ainsi recevoir une formation adéquate, lui permettant d'acquérir des connaissances techniques et juridiques, concernant par exemple l'usage de la force physique, le comportement à adopter vis-à-vis de certaines personnes et le respect des droits fondamentaux. Cette formation doit garantir que le personnel de sécurité exécute la tâche qui lui a été confiée dans le respect du principe de proportionnalité et de l'intégrité des personnes concernées, y compris lorsque celles-ci se comportent de manière inconvenante ou opposent une résistance physique. Elle vise également à éviter que certains agents de sécurité outrepassent leur rôle en cas d'intervention et à permettre une bonne collaboration avec la police. Une telle formation est d'autant plus nécessaire que pour obtenir l'autorisation d'engager un agent de sécurité, seules les conditions énumérées à l'art. 9 du concordat doivent être réunies. Le système d'autorisation et de formation mis en place par le concordat et l'arrêté permet ainsi de limiter les risques engendrés par l'exercice, à titre privé, de professions liées à la sécurité, ce qui constitue un intérêt public important. On ne saurait en effet tolérer que des tâches de sécurité soient effectuées par du personnel non formé ou n'étant pas titulaire d'une autorisation.
2.4 La recourante, dont le recourant est l'associé gérant et le responsable au sens de l'art. 7 al. 3 du concordat, a employé des agents de sécurité dont les autorisations étaient échues. Elle n'a en outre pas veillé à dispenser à ses employés la formation leur permettant d'exercer leur activité dans des conditions conformes au concordat et à l'arrêté. La suspension litigieuse a par ailleurs été précédée de deux avertissements formels prononcés les 9 août 2006 et 8 mai 2007, qui informaient le recourant des conséquences d'éventuels manquements ultérieurs. Au mois d'août 2006, celui-ci a été averti verbalement et rendu attentif à l'importance de ne pas négliger la formation de ses employés. Prononcée le 1er juillet 2008, la suspension litigieuse est ainsi intervenue plus d'une année après un second avertissement formel, ce qui laissait le temps nécessaire au recourant pour réorganiser son entreprise. Dans de telles conditions, il ne fait pas de doute que la sanction contestée est proportionnée. La décision de première instance datant maintenant de plusieurs années, les recourants ont eu largement le temps de prendre les mesures nécessaires pour faire face aux conséquences de la suspension en cause.
3. Pour ce qui est de l'"insécurité juridique" évoquée dans le recours (p. 3 et 4), il est précisé que la décision de suspension litigieuse concerne l'autorisation, dont la recourante est titulaire, d'exploiter une entreprise de sécurité, de sorte qu'un simple changement de responsable au sens de l'art. 7 al. 3 du concordat ne saurait avoir pour effet d'éviter la mise en ?uvre de la mesure.
4. Vu ce qui précède, le recours en matière de droit public doit être rejeté.
Succombant, les recourants doivent supporter les frais de la procédure devant le Tribunal fédéral, solidairement entre eux (cf. art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (cf. <ref-law>).
Avec le présent arrêt, la requête d'effet suspensif est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3. Le présent arrêt est communiqué au mandataire des recourants, à la Police cantonale, au Département de la justice, de la sécurité et des finances et au Tribunal cantonal du canton de Neuchâtel, Cour de droit public.
Lausanne, le 27 septembre 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Vianin