Sachverhalt:
A. A.a H._ (geboren 1958) und sein Bruder G._ (geboren 1960) waren seit 1993 und 1985 für die Firma N._ tätig. Anlässlich der Generalversammlung vom 24. Mai 2004 wurden sie mit sofortiger Wirkung als Verwaltungsräte der Aktiengesellschaft abberufen. Nachdem die Firma die von den Brüdern angesetzte Frist zur Sicherstellung noch nicht bezahlter Löhne unbenutzt hatte verstreichen lassen, lösten diese ihre Arbeitsverhältnisse mit Schreiben vom 30. Juli 2004 fristlos auf und leiteten Betreibung über die ausstehenden Gehaltsforderungen für die Monate April bis August 2004 im Gesamtbetrag von Fr. 32'255.- (H._) und Fr. 41'410.- (G._) ein. Gegen die Zahlungsbefehle vom 29. und 30. Juli 2004 erhob die ehemalige Arbeitgeberin Rechtsvorschlag.
Am 12. August 2004 stellten H._ und G._ bei der Arbeitslosenkasse des Kantons St. Gallen je Antrag auf Insolvenzentschädigung für nicht bezahlte Gehälter im Betrag von Fr. 37'359.- (H._) und Fr. 41'456.- (G._). Die Kasse lehnte die Begehren mit der Begründung ab, über die N._ sei bis heute kein Konkurs eröffnet worden; ausserdem entfalle eine Anspruchsberechtigung auch zufolge der bisherigen massgeblichen Stellung der Brüder im Betrieb der Aktiengesellschaft (Verfügungen vom 23. September 2004). Daran hielt sie auf Einsprache hin fest (Einspracheentscheide vom 19. November 2004). Das Sozialversicherungsgericht des Kantons Zürich (Entscheid vom 9. August 2005) und letztinstanzlich auch das damals zuständige Eidgenössische Versicherungsgericht (EVG; Urteil C 243/05 vom 16. Januar 2006) lehnten die dagegen erhobenen Beschwerden ab, wobei das EVG offen liess, ob und, bejahendenfalls, bis zu welchem Zeitpunkt H._ und G._ im Betrieb der ehemaligen Arbeitgeberin eine arbeitgeberähnliche Stellung eingenommen haben.
A.b Nachdem am 20. Februar 2007 über die N._ der Konkurs eröffnet worden war, stellten H._ und G._ am 26. Februar 2007 erneut Antrag auf Ausrichtung von Insolvenzentschädigung für entgangenen Verdienst während der Dauer vom 1. April bis 31. Juli 2004. Die Arbeitslosenkasse wies die Gesuche mit Verfügungen vom 30. April und 3. Mai 2007, bestätigt mit je einem Einspracheentscheid vom 11. Oktober 2007, ab, weil H._ und G._ bis am 22. Juni 2004 als Mitglied bzw. Vizepräsident des Verwaltungsrates im Handelsregister eingetragen gewesen seien und daher von Gesetzes wegen nicht anspruchsberechtigt seien; zudem habe die ehemalige Arbeitgeberin sie per 30. Juni 2004 freigestellt, was einen Insolvenzentschädigungsanspruch ebenfalls ausschliesse.
B. Das Sozialversicherungsgericht des Kantons Zürich wies die dagegen von H._ und G._ erhobene Beschwerde mit der Begründung ab, die Schadenminderungspflicht sei verletzt worden, weshalb die Kasse den Anspruch auf Insolvenzentschädigung im Ergebnis zu Recht verneint habe (Entscheid vom 14. April 2009).
C. H._ und G._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, es seien ihnen Insolvenzentschädigungen für entgangenen Verdienst in der Zeit vom 1. April bis 31. Juli 2004 nebst Zins zuzusprechen.
Die Arbeitslosenkasse schliesst auf Abweisung der Beschwerde. Das Staatssekretariat für Wirtschaft verzichtet auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>; vgl. auch <ref-law>; Ausnahme: Beschwerden gemäss <ref-law> [<ref-law>]). Wie die Sachverhaltsfeststellung ist auch die vorinstanzliche Ermessensbetätigung im Verfahren vor Bundesgericht nur beschränkt überprüfbar. Eine Angemessenheitskontrolle (vgl. <ref-ruling> E. 6 S. 81 [zu Art. 132 lit. a OG]) ist dem Gericht verwehrt; es hat nur zu prüfen, ob die Vorinstanz ihr Ermessen rechtsfehlerhaft ausgeübt, mithin überschritten, unterschritten oder missbraucht hat (vgl. <ref-ruling> E. 3.3 S. 399).
2. 2.1 Im vorinstanzlichen Entscheid werden die Bestimmungen und Grundsätze zum Anspruch auf Insolvenzentschädigung (Art. 51 Abs. 1 und Art. 58 AVIG; vgl. auch <ref-ruling>), zum Umfang des Anspruchs (<ref-law>) sowie zu den Pflichten des Arbeitnehmers im Konkurs- oder Pfändungsverfahren (<ref-law>; <ref-ruling> E. 3d S. 59; ARV 2002 Nr. 8 S. 62, C 91/01, und Nr. 30 S. 190, C 367/01; ARV 1999 Nr. 24 S. 140, C 183/97) zutreffend dargelegt. Darauf wird verwiesen.
2.2 Die Bestimmung von <ref-law>, wonach der Arbeitnehmer im Konkurs- oder Pfändungsverfahren alles unternehmen muss, um seine Ansprüche gegenüber dem Arbeitgeber zu wahren, bezieht sich dem Wortlaut nach auf das Konkurs- und Pfändungsverfahren. Sie bildet jedoch Ausdruck der allgemeinen Schadenminderungspflicht, welche auch dann Platz greift, wenn das Arbeitsverhältnis vor der Konkurseröffnung aufgelöst wird (<ref-ruling> E. 4 S. 60; ARV 1999 Nr. 24 S. 140, C 183/97). Eine ursprüngliche Leistungsverweigerung infolge Verletzung der Schadenminderungspflicht im Sinne der zu <ref-law> ergangenen Rechtsprechung setzt voraus, dass der versicherten Person ein schweres Verschulden, also vorsätzliches oder grobfahrlässiges Handeln oder Unterlassen vorgeworfen werden kann (vgl. URS BURGHERR, Die Insolvenzentschädigung, 2004, S. 166). Das Ausmass der geforderten Schadenminderungspflicht richtet sich nach den jeweiligen Umständen des Einzelfalls.
3. 3.1 Das kantonale Gericht hat in pflichtgemässer Würdigung der gesamten Aktenlage mit nachvollziehbarer Begründung erkannt, die Beschwerdeführer hätten keinen Anspruch auf Insolvenzentschädigung, weil sie in Verletzung der Schadenminderungspflicht nicht alles unternommen hätten, um ihre Ansprüche gegenüber der ehemaligen Arbeitgeberin zu wahren. Zwar seien nach der Auflösung der Arbeitsverhältnisse Ende Juli 2004 die Lohnforderungen umgehend gemahnt und in Betreibung gesetzt worden und - wenn man die Aneignung von Material der Arbeitgeberin durch die Beschwerdeführer als Versuch werten wolle, ausstehende Lohnguthaben durchzusetzen - diese Bemühungen hätten bis zum Entscheid des Bezirksgerichtes X._ vom 9. September 2004, mit welchem die erfolgte Rückgabe des Materials festgestellt worden sei, gedauert. Weder der nachfolgende Schriftenwechsel mit der Ausgleichskasse betreffend Beitragspflichtverletzung der Arbeitgeberin und Kinderzulagen zwischen November 2004 und Februar 2005 noch die Aufforderung zur Ausstellung von Lohnausweisen für das Jahr 2004 im März 2005 noch das von der Arbeitgeberin im Mai 2005 eingeleitete Betreibungsverfahren (Grund der geltend gemachten Forderung in der Höhe von Fr. 3'000'000.-: angebliche unerlaubte Handlungen und Schadenersatz aus Zusammenarbeit und Geschäftsführung) seien auf die Durchsetzung von Lohnansprüchen gerichtet gewesen. Die nächste zielgerichtete Handlung sei - nach über zehn Monaten - die erneute Einleitung der (Lohn-)Betreibungen im Juli 2005 (Zahlungsbefehle vom 29. Juli 2005) gewesen. Danach sei wiederum ein Jahr verstrichen bis zur Anhängigmachung des Rechtsöffnungsbegehrens am 28. Juli 2006. Konkursandrohung (Dezember 2006) und Konkurseröffnung (Februar 2007) seien wiederum zeitgerecht erfolgt. Die Phasen der Untätigkeit von zehn Monaten und einem Jahr seien um einiges länger als dies praxisgemäss toleriert werde, weshalb kein Anspruch auf Insolvenzentschädigung bestehe. Unter diesen Umständen konnte das kantonale Gericht offen lassen, ob den Beschwerdeführern auch wegen ihrer ehemaligen Stellung im Betrieb der Arbeitgeberin keine Insolvenzentschädigung zugestanden hätte.
3.2 Die Vorbringen der Beschwerdeführer vermögen diese Betrachtungsweise nicht in Zweifel zu ziehen. Die tatsächlichen Feststellungen der Vorinstanz sind nicht mangelhaft im Sinne von <ref-law> und die rechtliche Würdigung ist bundesrechtskonform.
3.2.1 Soweit die Beschwerdeführer letztinstanzlich einwenden, das kantonale Gericht habe völlig ausser Acht gelassen, dass ihre rasche Einleitung der Betreibungen (Ende Juli 2004) rechtsgenügliche Durchsetzungsmittel darstellten, welche zur Schadenminderung und Anspruchswahrung genügten, kann ihnen nicht gefolgt werden. Wie bereits im Urteil C 243/06 vom 16. Januar 2006 festgehalten, kann es nicht Sache der versicherten Person sein, darüber zu entscheiden, ob sie weitere Vorkehren zur Realisierung der Lohnansprüche treffen will und ob diese erfolgsversprechend sind oder nicht. Das für den Anspruch auf Insolvenzentschädigung gesetzlich vorgeschriebene fortgeschrittene Zwangsvollstreckungsverfahren ist entgegen der Ansicht der Beschwerdeführer durchaus sinnvoll, weil bekanntlich viele Schuldner erst unter dem Druck der unmittelbar bevorstehenden Konkurseröffnung oder Pfändung ihren Zahlungspflichten nachkommen (<ref-ruling> E. 4.1.2 S. 198). Die Entwicklung der Stellung der Beschwerdeführer im Betrieb, wie sie im letztinstanzlich eingereichten Rechtsmittel noch einmal dargelegt wird, ist im vorliegenden Zusammenhang lediglich insofern von Bedeutung, als für die ehemaligen Arbeitnehmer seit ihrer Kündigung der Arbeitsverhältnisse auf Ende Juli 2004 von vornherein klar war, dass die N._ die ausstehenden Löhne nicht freiwillig bezahlen würde. Mit anderen Worten wussten sie schon damals, dass betreibungsrechtliche und gerichtliche Schritte nötig sein würden, um ihre Lohnansprüche durchzusetzen. Die Einleitung der Betreibungen allein vermochte dabei die Anforderungen an die Schadenminderungspflicht nicht zu erfüllen. Die konsequente Durchsetzung der offenen Lohnforderungen auf dem Betreibungsweg und notwendigenfalls auch durch Einleitung von gerichtlichen Schritten kann von Versicherten in solchen Situationen gefordert werden, gerade wenn - wie vorliegend - die ehemalige Arbeitgeberin (nach den Erörterungen der Beschwerdeführer ungerechtfertigte) Gegenforderungen stellt und klar signalisiert, dass sie zur Begleichung der Lohnausstände nicht bereit sei. Nichts anderes kann sich aus dem Einwand ergeben, dass die Beschwerdeführer an einem Konkurs der Arbeitgeberin nicht interessiert gewesen seien, weil sie ihnen neben den ausstehenden Löhnen auch noch zu einem früheren Zeitpunkt gewährte Darlehen und andere Entschädigungen schuldete. Das Errreichen eines gesetzlich vorgeschriebenen fortgeschrittenen Zwangsvollstreckungsverfahrens (Art. 51 Abs. 1 und Art. 58 AVIG; E. 2.1 hiervor) bildet für den Anspruch auf Insolvenzentschädigung zwingende Voraussetzung.
3.2.2 Des Weiteren wird vorgebracht, die Arbeitslosenkasse treffe gemäss <ref-law> eine Aufklärungs- und Beratungspflicht und in diesem Rahmen hätten die Beschwerdeführer über die notwendigen Schritte informiert werden müssen. Dazu ist festzuhalten, dass sie spätestens durch die - die ersten leistungsablehnenden Verfügungen vom 23. September 2004 bestätigenden - Einspracheentscheide vom 19. November 2004 von der Arbeitslosenkasse darüber in Kenntnis gesetzt worden sind, dass ein Anspruch auf Insolvenzentschädigung wegen Nichterreichens des erforderlichen zwangsvollstreckungsrechtlichen Stadiums ("Demzufolge müsste erst der Rechtsvorschlag beseitigt werden, damit danach das Fortsetzungsbegehren resp. die Konkursandrohung und das Konkursbegehren gestellt werden können.") nicht bestehe. Abgesehen von der erneuten Anhebung von Lohnbetreibungen im Juli 2005 unternahmen die Beschwerdeführer daraufhin keine weiteren Bemühungen in diesem Zusammenhang. Das kantonale Gericht erkannte mit Entscheid vom 9. August 2005 ausdrücklich, dass es für einen Anspruch auf Insolvenzentschädigung an der vom Gesetz geforderten sachlichen Voraussetzung von <ref-law> fehle. Aber selbst nachdem das EVG letztinstanzlich rechtskräftig bestätigt hatte, dass das zwangsvollstreckungsrechtliche Verfahren nicht weit genug gediehen sei, um einen Anspruch auf Insolvenzentschädigung auszulösen (Urteil C 243/05 vom 16. Januar 2006), warteten die Beschwerdeführer mit den nächsten Schritten zur Durchsetzung ihrer Lohnforderungen weiter zu, bis sie Ende Juli 2006 die Betreibungsbegehren stellten. Obwohl sie demnach wussten, dass sie das zwangsvollstreckungsrechtliche Verfahren vorantreiben mussten, um Anspruch auf Insolvenzentschädigung zu erlangen, verliefen ihre Betreibungshandlungen äusserst zögerlich. Ihr Einwand bezüglich der mangelnden Aufklärung durch die Verwaltung ist damit rein theoretischer Natur, hatten sie doch bereits früh Kenntnis davon, dass eine der Anspruchsvoraussetzungen das Erreichen eines fortgeschrittenen zwangsvollstreckungsrechtlichen Stadiums darstellt. Dennoch hat das kantonale Gericht Phasen der Untätigkeit von zehn Monaten (September 2004 bis Juli 2005) und einem Jahr (Juli 2005 bis Juli 2006) feststellen müssen. Die Eröffnung des Konkurses (am 20. Februar 2007) liess nicht zuletzt darum so lange auf sich warten, weil die Beschwerdeführer, wie sie selber einräumen, wegen ihrer weiteren Forderungen gegenüber der ehemaligen Arbeitgeberin gar kein Interesse an deren Konkurs hatten.
3.2.3 Eine Auseinandersetzung mit den Argumenten der Beschwerdeführer zur Wahl der geeigneten Schritte bei der Durchsetzung der Lohnansprüche (provisorische Rechtsöffnung versus definitive Rechtsöffnung nach Zivilverfahren) kann unterbleiben, da der Ausgang des vorliegenden Prozesses nicht davon abhängt, auf welchem Weg und durch wen die Konkurseröffnung über die Gesellschaft ausgelöst wurde.
3.2.4 Schliesslich vermögen die Beschwerdeführer auch aus dem Hinweis auf Literatur und Rechtsprechung, woraus sie folgern, eine feste zeitliche Begrenzung des Anspruchs auf Insolvenzentschädigung sei unbillig, nichts zu ihren Gunsten abzuleiten. Die Vorinstanz nimmt keine Befristung der Insolvenzentschädigungsansprüche vor, indem sie eine zehnmonatige und eine einjährige Untätigkeit der Beschwerdeführer feststellt. Den Anspruch auf Insolvenzentschädigung verneint sie, weil durch das zögerliche Vorgehen nicht alles unternommen wurde, um das Recht auf den ausgebliebenen Lohn gegenüber der ehemaligen Arbeitgeberin zu wahren, was sie in nicht zu beanstandender Weise als Schadenminderungspflichtverletzung qualifiziert. Eine zumindest grobfahrlässige Unterlassung lässt sich insbesondere mit Blick auf die Untätigkeit in der Zeit nach Erlass des Urteils C 243/05 vom 16. Januar 2006 bis zur Stellung der Rechtsöffnungsbegehren Ende Juli 2006 nicht mehr verneinen.
3.3 Zusammenfassend ist den Beschwerdeführern beizupflichten, dass sie gleichzeitig mit der Auflösung ihrer Arbeitsverhältnisse zwar unmissverständliche Zeichen zur Geltendmachung ihrer Lohnforderungen setzten. Dies reicht aber zur Erfüllung der Schadenminderungspflicht nicht aus. Gefordert ist auch eine konsequente und kontinuierliche Weiterverfolgung der eingeleiteten Schritte, welche in einem der vom Gesetz geforderten zwangsvollstreckungsrechtlichen Stadien münden müssen, damit Anspruch auf Insolvenzentschädigung besteht. Die Vorbringen der Beschwerdeführer sind nicht geeignet, die vorinstanzliche Sachverhaltsfeststellung als offensichtlich unrichtig oder unvollständig erscheinen zu lassen. Von einer willkürlichen Beweiswürdigung durch die Vorinstanz kann ohnehin nicht gesprochen werden (<ref-ruling> E. 2b S. 56; vgl. auch <ref-ruling> E. 1.3 S. 4 f.). Das kantonale Gericht durfte demnach, ohne Bundesrecht zu verletzen, den Anspruch auf Insolvenzentschädigung ablehnen.
4. Dem Verfahrensausgang entsprechend sind die Gerichtskosten von den Beschwerdeführern zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von je Fr. 500.- werden den Beschwerdeführern auferlegt.
3. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich, dem Amt für Wirtschaft und Arbeit des Kantons Zürich und dem Staatssekretariat für Wirtschaft schriftlich mitgeteilt.
Luzern, 3. August 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Berger Götz