Sachverhalt:
A. A.a Am 1. Juli 2004 wurde die damals 22-jährige B._ von ihrem Ex-Freund C._ ermordet.
Das Strafgericht des Kantons Schwyz sprach den Täter mit Urteil vom 6. Juli 2006 des Mordes schuldig und verurteilte ihn zu einer lebenslänglichen Zuchthausstrafe. Dem Vater der Ermordeten, A._, sprach es eine Genugtuung in der Höhe von CHF 40'000.-- nebst 5 % Zins seit dem schädigenden Ereignis zu.
Eine vom Verurteilten gegen diesen Entscheid geführte Berufung wies das Kantonsgericht Schwyz mit Urteil vom 29. November 2006 ab und bestätigte das angefochtene Urteil des Strafgerichts auch im Zivilpunkt.
Das Bundesgericht wies die gegen das Urteil des Kantonsgerichts geführte staatsrechtliche Beschwerde sowie die Nichtigkeitsbeschwerde von C._ mit Urteil vom 29. Juni 2007 (6P.47/2007 und 6S.106/2007) ab, soweit es darauf eintrat.
A.b Am 20. Februar 2006 reichte A._ ein Gesuch um eine opferhilferechtliche Genugtuung im Betrag von CHF 50'000.-- ein.
Am 7. März 2007 verstarb A._.
Mit Beschluss vom 8. Januar 2008 wies der Regierungsrat des Kantons Schwyz das Gesuch um eine opferhilferechtliche Genugtuung mit der Begründung ab, dass an der leiblichen Vaterschaft von A._ Zweifel bestehen würden und dieser auch faktisch keine enge Beziehung zu seiner verstorbenen Tochter gehabt habe.
Gegen diesen Beschluss beschwerten sich die Kinder des verstorbenen A._, nämlich X._ und Y._ (Kinder aus der Ehe von A._ mit D._) sowie Z._ (Tochter von A._ und E._) beim Verwaltungsgericht des Kantons Schwyz und beantragten nebst der Aufhebung des Beschlusses die Zusprechung einer Genugtuung von insgesamt CHF 40'000.-- zuzüglich 5 % Zins seit dem 1. Juli 2004, eventualiter die Aufhebung des Beschlusses und die Rückweisung der Sache zu neuem Entscheid an die Vorinstanz.
Mit Entscheid vom 24. April 2008 (und Berichtigung des Urteilsdispositivs vom 30. Mai 2008) hiess die Kammer III des Verwaltungsgerichts die Beschwerde insofern teilweise gut, als dass der Genugtuungsanspruch von A._ sel. auf CHF 12'000.-- nebst Zins seit dem 1. Juli 2004 festgesetzt wurde, welcher seinen Erben (anteilsmässig) auszuzahlen sei (Dispositiv-Ziffer 1), und verpflichtete die Vorinstanz zur Bezahlung einer reduzierten Parteientschädigung an die Beschwerdeführer von insgesamt CHF 600.-- (Dispositiv-Ziffer 3). In der Urteilsbegründung führte das Verwaltungsgericht aus, grundsätzlich sei die Anspruchsberechtigung des Vaters des Opfers gegeben und die Vererblichkeit des Anspruchs auf die Erben ebenfalls zu bejahen. Entgegen der Ansicht des Regierungsrates müsse davon ausgegangen werden, dass A._ der leibliche Vater des Opfers sei. Auch habe sich dieser um seine Tochter gekümmert, so dass er auch faktisch als Vater zu betrachten sei. Die faktischen Eltern seien den leiblichen Eltern hinsichtlich des Genugtuungsanspruchs gleichgestellt. A._ habe eine normale, aber nicht überdurchschnittlich enge Bindung zu seiner Tochter gehabt. Unter Berücksichtigung opferhilferechtlicher Bemessungsgrundsätze sei eine Genugtuung in der Höhe von CHF 12'000.-- angemessen.
B. X._, Y._ und Z._ haben als Erbengemeinschaft gegen den Entscheid des Verwaltungsgerichts Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Die Beschwerdeführer beantragen, Dispositif-Ziffer 1 und 3 des angefochtenen Entscheids seien aufzuheben, und es sei ihnen zusammen eine Genugtuung von CHF 40'000.-- zuzüglich 5 % Zins seit dem 1. Juli 2004 sowie eine volle Parteientschädigung für das erstinstanzliche Gerichtsverfahren zuzusprechen, alles unter Entschädigungsfolgen zulasten der Vorinstanz.
C. Das Verwaltungsgericht verzichtet auf Vernehmlassung. Der Regierungsrat des Kantons Schwyz beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Justiz als beschwerdeberechtigte Bundesverwaltungsbehörde schliesst ebenfalls auf Beschwerdeabweisung. Die Beschwerdeführer verzichten auf eine weitere Stellungnahme.

Erwägungen:
1. Der angefochtene, kantonal letztinstanzliche Entscheid betrifft die Abweisung eines Gesuchs um eine finanzielle Leistung aufgrund des Opferhilfegesetzes des Bundes, d.h. eine öffentlich-rechtliche Angelegenheit im Sinne von <ref-law>. Ein Ausschlussgrund nach <ref-law> ist nicht gegeben. Das Opferhilfegesetz entspringt dem Gedanken der Hilfeleistung, nicht der Staatshaftung (<ref-ruling> E. 2.2.4 S. 121 mit Hinweisen). Nicht zum Tragen kommt demzufolge <ref-law>, wonach eine Beschwerde auf dem Gebiet der Staatshaftung nur zulässig ist, wenn der Streitwert nicht weniger als 30'000 Franken beträgt (Abs. 1 lit. a) oder sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt (Abs. 2). Die Sachurteilsvoraussetzungen sind insgesamt erfüllt. Auf die Beschwerde ist damit einzutreten.
2. Am 1. Januar 2009 ist das neue Bundesgesetz vom 23. März 2007 über die Hilfe an Opfer von Straftaten (Opferhilfegesetz, OHG; SR 312.5) in Kraft getreten. Nach dessen Übergangsbestimmung gilt das bisherige Recht für Ansprüche auf Entschädigung oder Genugtuung für Straftaten, die vor Inkrafttreten dieses Gesetzes verübt worden sind, wobei für Ansprüche aus Straftaten, die weniger als zwei Jahre vor dem Inkrafttreten dieses Gesetzes verübt worden sind, die Fristen nach Art. 25 gelten (<ref-law>).
Im vorliegenden Fall erfolgte die Straftat am 1. Juli 2004 und damit vor Inkrafttreten des neuen OHG am 1. Januar 2009. Zur Beurteilung des von den Beschwerdeführern geltend gemachten opferhilferechtlichen Genugtuungsanspruchs ist demzufolge das alte Opferhilfegesetz vom 4. Oktober 1991 in der bis zum 31. Dezember 2008 geltenden Fassung (aOHG) massgebend.
3. Strittig ist vorliegend die Bemessung der opferhilferechtlichen Genugtuung. Die Beschwerdeführer beanstanden, die Vorinstanz habe die Bemessungskriterien bundesrechtswidrig angewendet. Es habe das Leid des Vaters zu wenig berücksichtigt, sei hinsichtlich der Enge der Vater-Tochter-Beziehung vom Strafurteil abgewichen und habe bei der Festlegung der Genugtuungshöhe auf das neue, "deutlich opferunfreundlichere" statt auf das alte OHG abgestellt.
Das Bundesamt für Justiz dagegen erachtet die zugesprochene Genugtuung von CHF 12'000.-- angesichts der Umstände des Einzelfalles als angemessen. Unter Bezugnahme auf ein zur Zeit der Vernehmlassung hängiges Verfahren am Bundesgericht wirft es ausserdem die Frage auf, ob bei der Bemessung der Genugtuung als Reduktionsgrund hätte berücksichtigt werden müssen, dass der Vater des Opfers zur Zeit der Gutheissung des Genugtuungsanspruchs bereits verstorben war und seine Tochter nur um knapp drei Jahre überlebt hatte.
4. 4.1 Das Bundesgericht hat im Zusammenhang mit dem administrativen Führerausweisentzug Grundsätze dazu entwickelt, inwieweit die Verwaltungs- und Strafbehörden gegenseitig an ihre Erkenntnisse gebunden sind. Danach ist die Verwaltungsbehörde in reinen Rechtsfragen nicht an die Beurteilung durch das Strafgericht gebunden, da sie sonst in ihrer freien Rechtsanwendung beschränkt würde (Urteil des Bundesgerichts 1C_45/2007 vom 30. November 2007 E. 4.3, nicht publ. in: <ref-ruling>). Hingegen darf die Verwaltungsbehörde von den tatsächlichen Feststellungen des Strafgerichts nur abweichen, wenn sie aufgrund eigener Beweiserhebungen Tatsachen feststellt, die dem Strafgericht unbekannt waren oder die es nicht beachtet hat, ferner wenn neue entscheiderhebliche Tatsachen vorliegen, wenn die Beweiswürdigung des Strafgerichts feststehenden Tatsachen klar widerspricht oder wenn das Strafgericht bei der Rechtsanwendung auf den Sachverhalt nicht alle Rechtsfragen abgeklärt hat (Urteil 1C_45/2007, a.a.O., E. 4.3 mit Hinweisen).
4.2 Die Beschwerdeführer beanstanden, das Verwaltungsgericht habe in Abweichung von den Strafgerichten festgestellt, dass die Beziehung zwischen Vater und Tochter nicht überdurchschnittlich intensiv und harmonisch gewesen sei.
Laut Urteil des Kantonalen Strafgerichts Schwyz vom 6. Juli 2006 (E. VII.A.b.bb.bbb S. 83) hatte der Vater "eine gute Beziehung und ein enges Verhältnis" zu seiner getöteten Tochter. Sie hätten regelmässig Kontakt gehabt und seien sich nahe gestanden. Insbesondere der Tod der Mutter des Opfers im Jahr 2000 habe die Beziehung zwischen Vater und Tochter intensiviert. Hingegen habe die Getötete mit ihrem Vater nicht mehr in einem gemeinsamen Haushalt gelebt. Sie sei bereits erwachsen gewesen und habe auf eigenen Beinen gestanden. Dies rechtfertige es, dem Vater nicht eine Genugtuung in der geforderten Höhe, sondern eine Genugtuung von CHF 40'000.-- zuzusprechen.
Im Urteil vom 29. November 2006 (E. IV. S. 46) bestätigte das Kantonsgericht Schwyz das erstinstanzliche Urteil im Zivilpunkt unter Verweis auf die darin enthaltenen Erwägungen.
Das Verwaltungsgericht geht im angefochtenen Urteil (E. 3.3 S. 7-8 und E. 3.5 S. 10) gleich wie das Kantonale Strafgericht von einer guten, aber nicht überdurchschnittlich intensiven oder harmonischen Vater-Tochter-Beziehung aus. Diese Beurteilung stützt es, gleich wie die Strafgerichte, auf den Umstand, dass die Tochter (von kurzen Aufenthalten wegen Belästigungen und Drohungen ihres Ex-Freundes abgesehen) bereits seit längerem mit dem Vater nicht mehr im gleichen Haushalt gewohnt hatte. Gestützt auf die Akten und in Ergänzung der Strafurteile hielt das Verwaltungsgericht fest, dass der Vater der Getöteten das Verhältnis als gut bezeichnet habe. Unbestritten sei auch, dass die Getötete den Vater wenige Tage vor ihrem Tod mit ihren Kindern besucht und am Tag vor ihrer Ermordung mit ihm telefoniert habe (Urteil E. 3.3 S. 8). Indessen habe der Vater auch erwähnt, dass seine Tochter mit ihm nie über ihre Probleme gesprochen, er diese aber gekannt habe. Ferner stellte das Verwaltungsgericht fest, es gebe keine Anhaltspunkte dafür, dass der Vater bei der Lösung der diversen Probleme der Tochter aktiv Hilfe geleistet hätte, welcher Umstand bei der Bemessung der Genugtuung ebenfalls zu berücksichtigen sei (Urteil E. 3.5 S. 10).
Mit diesen Feststellungen setzt sich das Verwaltungsgericht in keinen Widerspruch zu den Feststellungen in den Strafurteilen, sondern ergänzt diese lediglich anhand der Akten. Es ist daher nicht ersichtlich, inwiefern das Verwaltungsgericht die in der Rechtsprechung entwickelten Grundsätze zum Umfang der Bindung der Verwaltungsbehörden an Strafurteile verletzt hätte.
5. 5.1 Nach Art. 12 Abs. 2 aOHG kann dem Opfer unabhängig von seinem Einkommen eine Genugtuung ausgerichtet werden, wenn es schwer betroffen ist und besondere Umstände es rechtfertigen. Der Ehegatte, die eingetragene Partnerin oder der eingetragene Partner des Opfers, dessen Kinder und Eltern sowie andere Personen, die ihm in ähnlicher Weise nahe stehen, werden dem Opfer bei der Geltendmachung von Entschädigung und Genugtuung gleichgestellt, soweit ihnen Zivilansprüche gegenüber dem Täter zustehen (Art. 2 Abs. 2 lit. c aOHG). Nach <ref-law> kann der Richter bei Tötung eines Menschen unter Würdigung der besonderen Umstände den Angehörigen des Getöteten eine angemessene Geldsumme als Genugtuung zusprechen. Der Genugtuungsanspruch ist vererblich (Bundesgerichtsurteil 1C_106/2008 vom 24. September 2008 E. 6.3, wobei dies nur für die nach Zivilrecht und nach altem OHG zugesprochenen Genugtuungen, hingegen nicht mehr nach neuem OHG gilt).
5.2 Für die Frage, ob und in welcher Höhe im Falle einer Tötung gestützt auf <ref-law> eine Genugtuung zugesprochen wird, ist nicht allein der Verwandtschaftsgrad, sondern vor allem die Intensität der Beziehung zwischen der getöteten Person und deren Angehörigen massgeblich (Roland Brehm, Berner Kommentar, 3. Aufl. 2006, N. 133 f. zu <ref-law>; Hardy Landolt, Zürcher Kommentar, 3. Aufl. 2007, N. 408 zu <ref-law>; Klaus Hütte, Anleitung zur Ermittlung angemessener Genugtuungsleistungen im Zivil- und im Opferhilferecht, in: Personen - Schaden - Forum 2005, S. 139 ff., S. 158 und S. 165). Die Höhe der zuzusprechenden Summe hängt massgeblich vom Ausmass der Beeinträchtigung des tatsächlichen Nähegefühls zwischen dem Getöteten und dem Anspruchsteller im Zeitpunkt der Tötung ab (Bundesgerichtsurteil 1C_106/2008, a.a.O., E. 3.2.2).
Der Tatsache, ob der Ansprecher mit dem Opfer zusammen gewohnt hat, kommt regelmässig eine grosse Bedeutung zu, weil darin ein wichtiger Anhaltspunkt für die Intensität einer Beziehung liegt (Bundesgerichtsurteile 1C_106/2008, a.a.O., E. 3.2.2; 1A.196/2000 vom 7. Dezember 2000, E. 3c, in: ZBl 102/2001 S. 492, je mit Hinweisen). Deshalb darf ein Abschlag vom Genugtuungsanspruch bei nicht bestehender Hausgemeinschaft zwischen erwachsenen Kindern mit eigenem Haushalt und ihren Eltern gemacht werden (Bundesgerichtsurteil 1C_106/2008, a.a.O., E. 3.2.2; Landolt, a.a.O., N. 429 und 451 zu <ref-law>; Hütte, a.a.O., S. 164).
Neben der Intensität der Beziehung ist die Dauer der Auswirkungen grundsätzlich ein wichtiges Bemessungskriterium (<ref-ruling> E. 2.2.2 mit Hinweisen). In aller Regel lässt das Alter des Hinterbliebenen keinen Rückschluss auf eine kürzere Leidenszeit zu. Steht jedoch zum Urteilszeitpunkt bereits fest, dass der genugtuungsberechtigte Angehörige das getötete Opfer nur um wenige Monate überlebt hat, so ist es nach bundesgerichtlicher Rechtsprechung zulässig, diesen Umstand genugtuungsmindernd zu berücksichtigen. Dies gilt zumindest dann, wenn kein Zusammenhang zwischen dem Tod des Opfers und demjenigen des Angehörigen besteht (Bundesgerichtsurteil 1C_106/2008, a.a.O., E. 5.3; vgl. auch <ref-ruling> E. 3.3 und 3.4 S. 127, wonach für die Bemessung der opferhilferechtlichen Genugtuung grundsätzlich der Urteilszeitpunkt massgeblich ist).
5.3 Nach der Rechtsprechung des Bundesgerichts zur Bemessung der opferhilferechtlichen Genugtuung sind die von den Zivilgerichten entwickelten Bemessungsgrundsätze zu <ref-law> (und <ref-law>) sinngemäss heranzuziehen (<ref-ruling> E. 2.2.1 S. 119 mit Hinweisen). Nach konstanter Gerichtspraxis braucht die Opferhilfe-Genugtuung aber nicht gleich hoch wie die zivilrechtliche zu sein, sondern darf tiefer angesetzt werden, da sie nicht vom Täter, sondern - im Sinne eines Akts der Solidarität zugunsten einer von Unrecht betroffenen Person - von der Allgemeinheit bezahlt wird (<ref-ruling> E. 2.2.4 S. 121 mit Hinweisen). Eine Reduktion gegenüber der zivilrechtlichen Genugtuung ist namentlich dann gerechtfertigt, wenn diese aufgrund von subjektiven, täterbezogenen Merkmalen (z.B. besonders skrupellose Art der Begehung der Straftat) erhöht worden ist (<ref-ruling> E. 2.2.4 S. 121 mit Hinweisen).
5.4 Das Verwaltungsgericht zitierte unter Bezugnahme auf die tabellarische Übersicht in Klaus Hütte/Petra Ducksch/Kayum Guerrero (Die Genugtuung, 3. Aufl., 8/05 III/1, Zeitraum 2003-2005) Gerichtsentscheide, in denen Eltern beim Verlust ihres Kindes eine opferhilferechtliche Basis-Genugtuung in der Höhe von CHF 22'000.-- bis CHF 25'000.-- zugesprochen worden war. Es nahm aber an, dass im vorliegenden Fall eine weniger intensive Beziehung zwischen Vater und Tochter bestanden habe, was eine Reduktion der Basis-Genugtuung rechtfertige.
Im Entscheid 1A.120/1999 vom 17. Januar 2000 waren der Mutter einer im eigenen Haushalt lebenden, getöteten Tochter CHF 25'000.-- Genugtuung zugesprochen worden; dabei wurden genugtuungserhöhend die Schwangerschaft der Tochter, das rücksichtslose Verhalten des Täters nach der Straftat sowie der Umstand berücksichtigt, dass die Mutter seither an starken Depressionen litt und jegliche Lebensfreude verloren hatte.
Im Entscheid 1A.169/2001 vom 7. Februar 2002 E. 5.2 schützte das Bundesgericht eine opferhilferechtliche Genugtuung von CHF 15'000.--, die der Mutter einer von ihrem Ehemann ermordeten Tochter zugesprochen worden war. Dabei wies es darauf hin, dass die opferhilferechtliche Genugtuung aufgrund ihrer Rechtsnatur und der Tatsache, dass sie von der Allgemeinheit und nicht vom Täter bezahlt wird, niedriger ausfallen kann als die zivilrechtliche Genugtuung (so auch <ref-ruling> E. 2.2.4 S. 121 und E. 3.3.3. S. 126 f. mit Hinweisen).
Im Urteil 1C_106/2008 vom 24. September 2008 E. 3.2 beurteilte das Bundesgericht eine Basis-Genugtuung von CHF 20'000.-- für den Vater eines Opfers, das seit mehr als 20 Jahren weit von den Eltern entfernt im eigenen Haushalt lebte, als vertretbar. Da der Vater das Opfer nur um wenige Monate überlebt hatte, erachtete das Bundesgericht eine Reduktion dieses Betrages auf CHF 5'000.-- ebenfalls als zulässig (E. 5).
5.5 Den kantonalen Behörden steht bei der Festsetzung der Höhe der Genugtuung ein weiter Ermessensspielraum zu, in den das Bundesgericht nur eingreift, wenn grundlos von den in Lehre und Rechtsprechung entwickelten Grundsätzen abgewichen wird, wenn Tatsachen berücksichtigt werden, die für den Entscheid im Einzelfall keine Rolle spielen dürfen oder wenn umgekehrt Umstände ausser Betracht geblieben sind, die hätten beachtet werden müssen, oder wenn sich der Entscheid als offensichtlich ungerecht erweist (<ref-ruling> E. 2.2.5 S. 121 mit Hinweisen).
5.6 Die Strafgerichte sprachen dem Vater des Opfers eine zivilrechtliche Genugtuung in der Höhe von CHF 40'000.-- zu. Dabei spielte das Verschulden des Straftäters eine massgebliche Rolle (vgl. das Strafurteil des Kantonsgerichts vom 29. November 2006 E. III.1.b S. 42 f. und E. IV S. 46). Bei der Bemessung der Opferhilfe-Genugtuung wird auf das Täterverschulden nicht abgestellt (vgl. E. 5.3 hiervor). Demzufolge ist bundesrechtlich nicht zu beanstanden, wenn das Verwaltungsgericht die skrupellose Art der Tötung (Mord) als Bemessungsfaktor nicht berücksichtigte und die opferhilferechtliche Genugtuung im Vergleich zur vom Straftäter zivilrechtlich geschuldeten Genugtuung tiefer ansetzte.
Das Verwaltungsgericht erwähnt neben der Basis-Genugtuung nach HÜTTE/DUKSCH/GUERRERO (CHF 22'000.-- bis CHF 25'000.-- bei Verlust eines Kindes) die Richtwerte zur Genugtuungsbemessung in der Botschaft vom 9. November 2005 zur Totalrevision des Bundesgesetzes über die Hilfe an Opfer von Straftaten (BBl 2005 7227: CHF 10'000.-- bis CHF 20'000.-- bei Verlust eines Kindes). Eines der Hauptziele der Gesetzesrevision lag darin, für die Kantone die Kosten einzugrenzen, die sich aus Genugtuungszahlungen ergeben (BBl 2005 7166, 7184, 7224 ff.). Die Beschwerdeführer beanstanden zu Recht, dass die Vorinstanz die weit tieferen Ansätze nach den Materialien zum neuen OHG als Vergleichsbasis heranzog, da für den vorliegend zu beurteilenden Genugtuungsanspruch für die vor dem 1. Januar 2009 begangene Straftat das alte OHG und somit höhere Genugtuungsansätze massgebend sind (<ref-law>; vgl. E. 2 hiervor).
Die Vorinstanz ging von einer intakten Vater-Tochter-Beziehung aus, berücksichtigte aber als genugtuungsreduzierend, dass die Verstorbene nicht das einzige Kind war, von kürzeren Aufenthalten abgesehen bereits seit ihrem 11. Lebensjahr nicht mehr mit dem Vater in einem gemeinsamen Haushalt lebte und ihr dieser bei der Lösung ihrer erheblichen Probleme keine aktive Hilfe geleistet hatte. Unter Berücksichtigung dieser Umstände erachtete das Verwaltungsgericht eine Genugtuung von CHF 12'000.-- als angemessen. Im Vergleich zu den (in E. 6.3 hiervor) erwähnten Präjudizien zur Höhe des Genugtuungsanspruchs beim Verlust eines erwachsenen, nicht mehr im gleichen Haushalt lebenden Kindes (CHF 15'000.-- im Entscheid 1A.169/2001, CHF 20'000.-- im Entscheid 1C_106/2008, CHF 25'000.-- im Entscheid 1A.120/1999) erscheint die zugesprochene Summe als eher niedrig.
Das Bundesamt für Justiz macht indessen zu Recht geltend, dass das Verwaltungsgericht bei der Bemessung der Genugtuung auch die kurze Dauer der Überlebenszeit des Vaters hätte einbeziehen müssen. Der Vater starb bereits knapp drei Jahre nach dem Tod seiner Tochter, was die Dauer seines Leidens erheblich verkürzte. Die Dauer des Leidens wirkt hier anspruchsreduzierend (vgl. E. 5.2 hiervor).
Im Urteil 1C_106/2008 E. 5.4 erachtete das Bundesgericht eine Reduktion der für den Vater, welcher das Opfer um wenige Monate überlebte, festgesetzten Basis-Genugtuung von CHF 20'000.-- auf CHF 5'000.-- nicht als ermessensmissbräuchlich. Im Ergebnis ist deshalb nicht zu beanstanden, dass das Verwaltungsgericht den auf die Erben übergehenden Genugtuungsanspruch (vgl. E. 5.1 hiervor) auf CHF 12'000.-- nebst Zins seit dem schädigenden Ereignis festsetzte. Das Bundesgericht hat keinen Anlass, in den Ermessensspielraum der Vorinstanz einzugreifen.
6. Nach dem Gesagten erweist sich die Beschwerde als unbegründet und ist abzuweisen.
Im Bereich des Verfahrensrechts gilt der Grundsatz, dass das Rechtsmittelverfahren nach dem bisherigen Recht weitergeführt wird (Urteil des Bundesgerichts vom 30. September 1997 E. 3c, in: Pra 1998 Nr. 20 S. 145; ALFRED KÖLZ/ISABELLE HÄNER, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2. Aufl. 1998, Rz. 79; Alfred Kölz, Intertemporales Verwaltungsrecht, in: ZSR 102/1983 II S. 222 f.). Vorliegende Beschwerde in öffentlich-rechtlichen Angelegenheiten wurde mit Eingabe vom 26. Juni 2008 (Datum Poststempel), somit vor dem Inkrafttreten des neuen OHG am 1. Januar 2009 beim Bundesgericht hängig gemacht. Demnach kommen die Verfahrensbestimmungen des alten OHG, d.h. Art. 16 aOHG auf das Verfahren zur Anwendung. Nach der Rechtsprechung zu Art. 16 Abs. 1 aOHG ist das Verfahren vor Bundesgericht kostenlos (<ref-ruling> E. 4b S. 218 f.).
Die Zusprechung einer Parteientschädigung fällt ausser Betracht (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Dieses Urteil wird den Beschwerdeführern, dem Regierungsrat und dem Verwaltungsgericht des Kantons Schwyz, Kammer III, sowie dem Bundesamt für Justiz, Direktionsbereich Öffentliches Recht, schriftlich mitgeteilt.
Lausanne, 1. April 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Schoder