Sachverhalt: A. Die Staatsanwaltschaft III Zürich führt eine Strafuntersuchung gegen A._ und weitere Angeschuldigte u.a. wegen Veruntreuung eines Teils des Aktien- und Partizipationsscheins-Kapitals der B._ AG, Rapperswil-Jona. Ausgelöst wurde das Verfahren durch eine Strafanzeige von X._ und Y._ wegen Betrugs. Darin wurde den Angeschuldigten vorgeworfen, sie hätten die Anzeigeerstatter veranlasst, Aktionäre der B._ AG zu werden, die Eigentümerin des "Goldenen Chiemsee-Kessels" sei, eines bedeutenden kulturellen und kunsthistorischen Fundobjekts mit einem Kommerzialisierungswert von über einer Milliarde Euro. Allerdings sei den Anzeigeerstattern lediglich eine wertlose Replik präsentiert worden. Sie seien dadurch zu Investitionen in Höhe von 1.1 Mio. Euro in die Vermarktung des Kulturobjekts verleitet worden, für welche sie nie einen Gegenwert erhalten hätten. Beim "Goldenen Chiemsee-Kessel" handelt es sich um einen im Chiemsee (in Bayern, Deutschland) entdeckten, ca. 11 kg schweren Kessel aus Goldblech, der mit keltischen Motiven verziert ist. Herkunft und Alter des Kessels sind streitig. B. Mit Verfügung vom 28. November 2006 wurde der Chiemsee-Kessel von der zuständigen Strafverfolgungsbehörde als Beweismittel und zur allfälligen Deckung von Verfahrenskosten, Schadensdeckung etc. beschlagnahmt. Am 30. April 2008 wies die Staatsanwaltschaft III des Kantons Zürich (im Folgenden: Staatsanwaltschaft) den Antrag auf Herausgabe des Chiemsee-Kessels an die B._ AG ab. Diese Verfügung zog sie am 23. Mai 2008 in Wiedererwägung und ordnete, aus Gründen der Verhältnismässigkeit, um die Vermarktung des Chiemsee-Kessels nicht zu gefährden, dessen Herausgabe an die B._ AG an, unter Vorbehalt einer anderslautenden zivilrechtlichen Verfügung. Als Ersatzmassnahmen wurde die Beschlagnahme des Erlöses aus dem allfälligen Verkauf des Chiemsee-Kessels angeordnet und der B._ AG und A._ diesbezüglich verschiedene Weisungen auferlegt. Gegen diese Freigabeverfügung erhoben X._ und Y._ Rekurs an die Oberstaatsanwaltschaft des Kantons Zürich. Überdies machten Drittansprecher mit Rekurs bzw. Wiedererwägungsgesuch selbständige Besitzrechte an dem Objekt geltend. Die Oberstaatsanwaltschaft leitete die Rekursschriften dem Einzelrichter in Strafsachen des Bezirksgerichts Meilen weiter, der nach § 97 StPO/ZH zuständig sei, sofern die Beschlagnahme bzw. die Freigabe einen nicht wiedergutzumachenden Nachteil bewirke. Am 23. September 2008 erliess die Staatsanwaltschaft eine 2. Wiedererwägungsverfügung. Sie hob ihre Freigabeverfügung vom 23. Mai 2008 auf und beantragte dem Einzelrichteramt des Bezirks Zürich, es sei die Hinterlegung des sogenannten "Goldenen Chiemsee-Kessels" zu genehmigen und es seien die für die Herausgabe erforderlichen Verfügungen zu erlassen. Gleichzeitig verfügte die Staatsanwaltschaft, dass der Chiemsee-Kessel bis zum Entscheid über den Hinterlegungsantrag unter Beschlag bleibe. Der Einzelrichter in Strafsachen des Bezirksgerichts Meilen schrieb daraufhin den bei ihm hängigen Rekurs von X._ und Y._ als gegenstandslos geworden ab. Gegen die Verfügung vom 23. September 2008 rekurrierte der Angeschuldigte A._. Auf dessen Rekurs trat die Oberstaatsanwaltschaft am 16. Oktober 2008 nicht ein. C. Am 25. Februar 2009 trat die Einzelrichterin am Bezirksgericht Zürich auf den Hinterlegungsantrag der Staatsanwaltschaft nicht ein. Sie führte aus, die Staatsanwaltschaft könne den Drittansprechern Frist zur Einreichung von Zivilklagen ansetzen und müsse nicht den "Umweg" über die Hinterlegungsrichterin nehmen. Daraufhin setzte die Staatsanwaltschaft am 6. April 2009 den Drittansprechern eine Frist von 30 Tagen, um Ansprüche betreffend den Chiemsee-Kessel im Rahmen einer Zivilklage gegen die B._ AG geltend zu machen; falls innerhalb dieser Frist keine diese Ansprüche sichernde zivilprozessuale vorsorgliche Massnahme erwirkt werde, werde der Chiemsee-Kessel der B._ AG herausgegeben. Die Staatsanwaltschaft beschlagnahmte den Erlös aus einem allfälligen Verkauf des Chiemsee-Kessels und wies die B._ AG und A._ an, sie stets unverzüglich über Standortwechsel des Kessels sowie über wesentliche Entwicklungen des Verkaufsprozesses zu orientieren. Zudem sei ein schweizerisches Bankkonto zu bestimmen, welches die Staatsanwaltschaft sperren könne, und der allfällige Käufer sei anzuweisen, Zahlungen für den Kessel ausschliesslich auf dieses Konto zu leisten. D. Gegen diese Verfügung rekurrierten X._ und Y._ am 15. April 2009 an die Oberstaatsanwaltschaft des Kantons Zürich. Diese wies den Rekurs am 18. Juni 2009 ab, soweit sie darauf eintrat. Sie vertrat die Auffassung, die strafprozessuale Freigabe des Objekts sei bereits mit Verfügung vom 23. September 2008 erfolgt. Bei der angefochtenen Verfügung handle es sich deshalb um eine reine Vollzugsverfügung, weshalb auf die Rügen der Rekurrenten zum strafprozessualen Beschlag und den von der Staatsanwaltschaft vorgesehenen Ersatzmassnahmen nicht mehr eingetreten werden könne. E. Gegen diesen Entscheid haben X._ und Y._ am 20. Juli 2009 Beschwerde in Strafsachen an das Bundesgericht erhoben. Sie beantragen, der Rekursentscheid der Oberstaatsanwaltschaft und die Verfügung der Staatsanwaltschaft vom 6. April 2009 seien aufzuheben. Eventualiter sei nur der Rekursentscheid aufzuheben und die Sache zur materiellen Behandlung an die Oberstaatsanwaltschaft zurückzuweisen. Überdies ersuchen sie um Gewährung der aufschiebenden Wirkung. Die Beschwerdeführer vertreten die Auffassung, der Chiemsee-Kessel sei erst mit Verfügung vom 6. April 2009 aus der strafprozessualen Beschlagnahme entlassen worden, weshalb die Oberstaatsanwaltschaft auf ihre materiellen Rügen hätte eintreten müssen. F. Die Staatsanwaltschaft beantragt, der angefochtene Entscheid der Oberstaatsanwaltschaft sei zu bestätigen. Die Oberstaatsanwaltschaft hat auf eine Vernehmlassung verzichtet.