Sachverhalt:
A. Am 11. Oktober 2010 erliess das Steueramt der Gemeinde A._ gegen die Eheleute X._ und Y._ eine Sicherstellungsverfügung über Fr. 5'160'000.-- zur Deckung der Staats- und Gemeindesteuern 2004 bis 2009. Gleichzeitig übermittelte das Steueramt die Sicherstellungsverfügung als Arrestbefehle den Betreibungsämtern B._ und A._.
Mit Rekurs vom 11. November 2010 an das Verwaltungsgericht des Kantons Zürich beantragten X._ und Y._ u.a., die Sicherstellungsverfügung sei aufzuheben, eventualiter sei der sicherzustellende Betrag auf Fr. 1'500'000.-- zu reduzieren; der Arrestbefehl des Steueramtes A._ vom 11. Oktober 2010 sei aufzuheben und die Vorinstanz anzuweisen, beim Betreibungsamt die Aufhebung der Arrestierung zu veranlassen.
Mit Urteil vom 25. Mai 2011 erkannte das Verwaltungsgericht wie folgt:
1. Der Rekurs wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtsgebühr wird festgesetzt auf
Fr. 50'000.--; die übrigen Kosten betragen:
Fr. 120.-- Zustellkosten
Fr. 50'120.-- Total der Kosten.
3. Die Gerichtskosten werden den Rekurrierenden je zur Hälfte auferlegt, unter solidarischer Haftung für die gesamten Kosten.
4. Eine Parteientschädigung wird nicht zugesprochen.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen X._ und Y._ dem Bundesgericht, die Dispositivziffern 2 und 4 des Urteils des Verwaltungsgerichts vom 25. Mai 2011 seien aufzuheben; die Gerichtsgebühr sei auf das zulässige Mass zu reduzieren und es sei eine angemessene Parteientschädigung zuzusprechen; eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Kantonale Steueramt Zürich, das Gemeindesteueramt A._ und das Verwaltungsgericht des Kantons Zürich beantragen Abweisung der Beschwerde (soweit darauf einzutreten sei).
Mit Eingabe vom 24. Oktober 2011 reichten die Beschwerdeführer Bemerkungen zu den eingegangenen Vernehmlassungen ein.

Erwägungen:
1. 1.1 Über Rekurse gegen Sicherstellungsverfügungen der Gemeindesteuerämter für die kantonalen Steuern entscheidet im Kanton Zürich das Verwaltungsgericht als einzige Gerichtsinstanz (Art. 181 Abs. 3 des Steuergesetzes vom 8. Juni 1997, nachfolgend StG). Es handelt sich um eine letzte, obere kantonale Instanz im Sinne von <ref-law>. Das Verwaltungsgericht hat den Rekurs abgewiesen, soweit darauf einzutreten war, und damit das Sicherstellungsverfahren für die Staats- und Gemeindesteuern auf kantonaler Stufe, unter Vorbehalt des Weiterzugs ans Bundesgericht, abgeschlossen. Nach der Rechtsprechung stellt der verfahrensabschliessende Entscheid über die Sicherstellungsverfügung einen Endentscheid im Sinne von <ref-law> dar (<ref-ruling> E. 1.4). Die Beschwerdeführer sind durch den angefochtenen Entscheid in ihren rechtlich geschützten Interessen betroffen und zur Beschwerde berechtigt (<ref-law>). Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>), die auch den übrigen Prozessvoraussetzungen genügt, ist einzutreten.
1.2 Mit der Beschwerde kann nach <ref-law> die Verletzung von Bundesrecht gerügt werden, von kantonalem Recht nur in den Fällen von lit. c-e dieser Vorschrift. Die Verletzung von kantonalem Recht bildet keinen eigenständigen Rügegrund. Angefochten ist hier der vorinstanzliche Entscheid nur hinsichtlich der Gerichtskosten und der Parteientschädigung. Diese richten sich nach dem kantonalen Verfahrensrecht. Mit der vorliegenden Beschwerde kann daher nur geltend gemacht werden, die Kosten- und Entschädigungsregelung gemäss dem angefochtenen Entscheid verstosse gegen verfassungsmässige Rechte und Grundsätze der Bundes- oder Kantonsverfassung (Art. 95 lit. a und c BGG; <ref-ruling> E. 1.2 S. 145; <ref-ruling> E. 4.2.2 S. 158). Hierfür gilt eine gegenüber der allgemeinen Begründungspflicht (<ref-law>) qualifizierte Rügepflicht (<ref-law>). Mit der gleichen beschränkten Kognition wäre übrigens die Sicherstellungsverfügung gemäss <ref-law> auch dann zu prüfen, wenn sie in materieller Hinsicht angefochten worden wäre (vgl. <ref-ruling> E. 3).
2. 2.1 Die Beschwerdeführer rügen eine Verletzung ihres Anspruchs auf rechtliches Gehör, begangen dadurch, dass das Verwaltungsgericht zur Begründung seines Entscheids über die Kosten- und Entschädigungsfolgen einzig auf die anwendbaren gesetzlichen Normen verwiesen habe. Es gehe aus dieser Begründung nicht hervor, ob das Verwaltungsgericht den Tarif für Verfahren mit bestimmbarem Streitwert oder denjenigen für die übrigen Verfahren angewendet habe.
Aus dem Anspruch auf rechtliches Gehör fliesst die Pflicht zur Begründung von Verfügungen. Die Begründung muss so abgefasst sein, dass der Betroffene den Entscheid gegebenenfalls sachgerecht anfechten kann (<ref-ruling> E. 3.3 S. 445 mit Hinweis). Die erforderliche Begründungsdichte hängt dabei eng mit der Frage zusammen, ob die Vorinstanz die Gebühr im üblichen Rahmen gemäss Gebührentarif festzusetzen hatte oder ob im Gegenteil ausserordentliche Umstände zu berücksichtigen waren. Die formelle Rüge kann vorliegend daher nicht losgelöst von der Überprüfung der Gebühr in materieller Hinsicht geprüft werden und ist zusammen mit dieser zu behandeln (vgl. nachfolgende E. 3).
2.2 Die Beschwerdeführer machen ferner geltend, im Sicherstellungsverfahren sei ihnen der Anspruch auf rechtliches Gehör nicht gewährt worden, sondern erst im Verfahren vor dem Verwaltungsgericht. Sie hätten daher - selbst bei Abweisung des Rekurses - Anspruch darauf, dass ihnen keine Kosten auferlegt werden und eine Parteientschädigung zugesprochen wird. Auf dieses bereits im Rekursverfahren vorgebrachte Argument sei die Vorinstanz in der Urteilsbegründung mit keinem Wort eingegangen. Auch in diesem Punkt sei der angefochtene Entscheid ungenügend begründet.
Vor Erlass einer in die Rechtstellung eingreifenden Verfügung ist grundsätzlich das rechtliche Gehör und insbesondere das Äusserungsrecht zu gewähren (<ref-law>; <ref-ruling> E. 5.5-5.7). Dringlichkeit oder überwiegende öffentliche oder private Interessen können aber ausnahmsweise gebieten, das rechtliche Gehör erst nach der getroffenen Massnahme oder Verfügung einzuräumen (Gerold Steinmann in: Die schweizerische Bundesverfassung, 2. Aufl. 2008, N. 22 zu <ref-law> mit Hinweis auf <ref-ruling> E. 11 S. 296 ff. und 104 Ia 69). Der Zweck der Sicherstellungsverfügung würde offensichtlich vereitelt, wenn die Steuerpflichtigen vor Erlass und Vollstreckung der Verfügung zur Stellungnahme eingeladen würden. Es bedeutet folglich keine Verletzung des Anspruchs auf rechtliches Gehör, wenn die Beschwerdeführer erst nachträglich, im Rechtsmittelverfahren vor dem Verwaltungsgericht, ihren Standpunkt darlegen und ihre Verteidigungsmittel vorbringen konnten.
2.3 Aus dem gleichen Grund ist auch nicht ersichtlich, inwiefern das Verwaltungsgericht den in der Sache unterlegenen Beschwerdeführern - und entgegen der gesetzlichen Regelung (§ 152 und § 181 Abs. 3 StG in Verbindung mit §17 Abs. 2 des Verwaltungsrechtspflegegesetzes vom 24. Mai 1959) - eine Parteientschädigung hätte zusprechen müssen. Soweit die Beschwerdeführer beantragen, die Dispositivziffer 4 im angefochtenen Entscheid (Parteientschädigung) sei aufzuheben, ist die Beschwerde unbegründet. Die Beschwerde ist in diesem Punkt abzuweisen.
2.4 Die Beschwerdeführer berufen sich auch auf den Grundsatz von Treu und Glauben nach <ref-law>. Sie machen geltend, die Kostenvorschussverfügung bilde Vertrauensgrundlage dafür, dass die Gerichtsgebühr jedenfalls nicht mehr als Fr. 10'000.-- betragen würde. Inwiefern aus der Verfügung über den Kostenvorschuss eine Vertrauensgrundlage abgeleitet werden kann, wird in der Beschwerde jedoch nicht dargelegt. Der Kostenvorschuss, der von den Parteien nach Einreichung der Beschwerde oder auch im Laufe des Verfahrens eingefordert wird, dient der Sicherstellung der mutmasslich zu erwartenden Gerichtskosten. Er wird im Rahmen der Prozessleitung festgelegt und kann den Parteien auch als Orientierung der zu erwartenden Kosten dienen. Er ist für das Gericht dennoch nicht bindend (s. auch <ref-ruling> E. 4 S. 244 ff.). Dieses hat vielmehr die Gerichtsgebühr entsprechend dem Streitwert, dem Aufwand, der Bedeutung und Schwierigkeit des Falles und den weiteren für die Bemessung der Gerichtsgebühr massgebenden Faktoren festzulegen. Damit kann aber die Verfügung für den Kostenvorschuss keine Vertrauensgrundlage für eine bestimmte oder eine maximale Höhe der Gebühr abgeben.
3. 3.1 Bei den Gerichtskosten handelt es sich um Kausalabgaben (<ref-ruling> E. 3.1; <ref-ruling> E. 4.2 S. 121; <ref-ruling> E. 4a S. 244; <ref-ruling> E. 2a S. 174). Als solche bedürfen sie der Grundlage in einem formellen Gesetz, das zumindest den Kreis der Abgabepflichtigen sowie Gegenstand und Bemessungsgrundlage der Abgabe festlegt. Diese Anforderungen dürfen für gewisse Kausalabgaben - was die Abgabenbemessung (nicht aber Umschreibung des Kreises der Abgabepflichtigen und des Gegenstandes der Abgabe) anbelangt - in bestimmten Fällen herabgesetzt werden. Das gilt namentlich dort, wo das Mass der Abgabe durch überprüfbare verfassungsrechtliche Prinzipien (Kostendeckungs- und Äquivalenzprinzip) begrenzt wird und nicht allein der Gesetzesvorbehalt diese Schutzfunktion erfüllt (BGE <ref-ruling> E. 4.2 S. 121; <ref-ruling> E. 2.1 S. 374 f.; <ref-ruling> E. 2.2; <ref-ruling> E. 2 mit zahlreichen Hinweisen).
Einer solchen Lockerung zugänglich sind grundsätzlich auch Vorschriften über Verfahrenskosten und insbesondere über Gerichtsgebühren (BGE <ref-ruling> E. 4.2; <ref-ruling> E. 2a).
3.2 Die Beschwerdeführer beanstanden, dass die Bemessungsgrundlage für die hier streitige Gerichtsgebühr nur in der Gebührenverordnung des Verwaltungsgerichts enthalten sei, nicht aber im formellen Gesetz.
Das trifft offensichtlich nicht zu: Gemäss § 2 der Gebührenverordnung des Verwaltungsgerichts vom 23. August 2010 (GebV VGr) bemisst sich die Gerichtsgebühr "nach dem Zeitaufwand des Gerichts, der Schwierigkeit des Falles und dem Streitwert oder dem tatsächlichen Streitinteresse". Diese Umschreibung lautet praktisch wörtlich gleich wie der Absatz 1 des neu in das Steuergesetz aufgenommenen § 150b StG, in Kraft seit 1. Januar 2011. Die Beschwerdeführer übersehen offensichtlich, dass gleichzeitig mit der Einführung der neuen Gebührenverordnung per 1. Januar 2011 auch das kantonale Steuergesetz vom 8. Juni 1997 u.a. mit einem neuen Artikel 150b ergänzt wurde (gemäss Gesetz vom 13. September 2010). Auch der Gebührenrahmen von Fr. 500.-- bis Fr. 50'000.-- (§ 3 GebV VGr) ist durch Absatz 2 von Art. 150b StG gesetzlich vorgegeben.
Entgegen der Ansicht der Beschwerdeführer kann auch von einer übermässigen Bandbreite - und damit Unbestimmtheit - des Gebührentarifs keine Rede sein. Für Verfahren mit bestimmbarem Streitwert sieht die Gebührenverordnung des Verwaltungsgerichts innerhalb des gesetzlichen Gebührenrahmens von Fr. 500.-- bis Fr. 50'000.--, abgestuft nach Streitwert, insgesamt neun Klassen vor. Für die höchste Klasse, d.h für Streitwerte über einer Million Franken, beträgt die Gebühr Fr. 20'000.-- bis Fr. 50'000.-- (vgl. § 3 GebV VGr). Dabei ist die Gebühr "nach dem Zeitaufwand des Gerichts, der Schwierigkeit des Falles und dem Streitwert oder dem tatsächlichen Streitinteresse" zu bemessen (§ 150b Abs. 1 StG resp. § 2 GebV VGer). Weshalb es dem Verwaltungsgericht nicht möglich sein soll, diese Vorgaben sachgerecht umzusetzen und bei der Festsetzung der Gebühr sein Ermessen pflichtgemäss zu betätigen, legen die Beschwerdeführer aber nicht dar. Auf die Rüge der fehlenden gesetzlichen Grundlage und mangelnden Bestimmtheit des Gesetzes ist nicht weiter einzugehen (<ref-law>).
3.3 Näherer Betrachtung bedarf indessen das Äquivalenzprinzip, das ebenfalls als verletzt gerügt wird.
Das Äquivalenzprinzip konkretisiert das Verhältnismässigkeitsprinzip und das Willkürverbot (Art. 5 Abs. 2 und <ref-law>) für den Bereich der Kausalabgaben. Es bestimmt, dass eine Gebühr nicht in einem offensichtlichen Missverhältnis zum objektiven Wert der Leistung stehen darf und sich in vernünftigen Grenzen halten muss. Der Wert der Leistung bemisst sich nach dem wirtschaftlichen Nutzen, den sie dem Pflichtigen bringt, oder nach dem Kostenaufwand der konkreten Inanspruchnahme im Verhältnis zum gesamten Aufwand des betreffenden Verwaltungszweigs, wobei schematische, auf Wahrscheinlichkeit und Durchschnittserfahrungen beruhende Massstäbe angelegt werden dürfen. Es ist nicht notwendig, dass die Gebühren in jedem Fall genau dem Verwaltungsaufwand entsprechen; sie sollen indessen nach sachlich vertretbaren Kriterien bemessen sein und nicht Unterscheidungen treffen, für die keine vernünftigen Gründe ersichtlich sind (zum Ganzen <ref-ruling> E. 2.3 S. 228 mit weiteren Hinweisen; ferner <ref-ruling> E. 2a).
Bei Gerichtsgebühren ist ausserdem der Anspruch auf Zugang zum Gericht (<ref-law>), der durch die Auferlegung von Kosten nicht ungebührlich erschwert werden darf, zu beachten. Das gilt namentlich dann, wenn es für den Betroffenen darum geht, sich erstmals rechtliches Gehör zu verschaffen. Zum Anspruch auf rechtliches Gehör, wie er in <ref-law> enthalten ist, gehört insbesondere, dass der Betroffene vor Erlass einer Verfügung, die in seine Rechtsstellung eingreift, sich zur Sache äussern kann (<ref-ruling> E. 3.1 S. 370; <ref-ruling> E. 2.2 S. 505; Urteil 8C_322/2009 vom 9. September 2009). Sofern im Rahmen einer vorsorglichen Massnahme das rechtliche Gehör nicht vorgängig gewährt werden kann, muss der Betroffene daher auch noch bei der nachfolgenden gerichtlichen Überprüfung Stellung nehmen können. So sieht beispielsweise auch Art. 265 der Schweizerischen Zivilprozessordnung [ZPO; SR 272] für superprovisorische Massnahmen vor, dass mit der Anordnung der Massnahme die Parteien vorgeladen oder zur Stellungnahme eingeladen werden und danach neu entschieden wird. Gleiches muss grundsätzlich auch für vorsorgliche Massnahmen im Verwaltungsverfahren gelten (Regina Kiener, in: Kommentar zum Bundesgesetz über das Verwaltungsverfahren, 2008, N. 12 zu <ref-law>, mit weiteren Hinweisen; Hansjörg Seiler, in: Praxiskommentar zum Bundesgesetz über das Verwaltungsverfahren, 2009, N. 65 zu <ref-law>;). Dann muss aber auch darauf geachtet werden, dass der Zugang zum Gericht und die Ausübung des Gehörsanspruchs nicht durch hohe Kosten übermässig erschwert wird.
3.4 Vorliegend hat das Verwaltungsgericht in Auslegung von § 181 StG erwogen, ein bestimmtes, die Steuerforderung gefährdendes Verhalten des Steuerpflichtigen sei für die Steuersicherung bzw. Sicherstellung nicht erforderlich. Es genüge vielmehr bereits, wenn die Zwangsvollstreckung als erschwert erscheine. Ob eine Steuerpflicht in der Schweiz und eine Steuerforderung in der sichergestellten Höhe bestehen und ob die Steuer gefährdet erscheine, prüfe das Gericht zudem nur unter dem Gesichtswinkel der Glaubhaftmachung (prima facie). Das Verwaltungsgericht nahm diese Prüfung im Wesentlichen anhand der von den Beschwerdeführern eingereichten Steuererklärungen vor. Es hat eine Steuergefährdung bejaht, weil das Vermögen der Beschwerdeführer in der Schweiz in leicht verschiebbaren Bankguthaben, Wertschriften und Beteiligungen bestehe und sich der Beschwerdeführer bereits am 31. Dezember 2009 ins Ausland abgemeldet habe.
3.5 Diese Begründung ist hier materiell nicht zu prüfen. Fraglich ist nur, ob sich eine Gerichtsgebühr in der Höhe von Fr. 50'000.-- rechtfertigen lässt. Es handelt sich um die höchstmögliche Gebühr, die im Verfahren vor dem Verwaltungsgericht in der Regel ausgesprochen werden darf (vgl. § 150b Abs. 2 StG). Für eine erstmalige Anhörung der Beschwerdeführer über die getroffene Massnahme ist diese Gebühr aber unverhältnismässig hoch. Der Zugang zum Gericht und damit auch das rechtliche Gehör würden offensichtlich erheblich beeinträchtigt, wenn für die erstmalige Anhörung in einer Sache bereits die höchstmögliche Gebühr verlangt wird.
Wohl ist hier auch der hohe Streitwert mit zu berücksichtigen. Zu beachten ist aber, dass es noch in keiner Weise um das Hauptverfahren oder auch nur um das Vorverfahren auf Feststellung der Steuerhoheit und der Steuerpflicht geht. Vielmehr erfolgt diese Prüfung in einem separaten Verfahren, wie die Vorinstanz zutreffend ausführt. Tatsachenprüfung und Begründung durch das Verwaltungsgericht beschränkten sich zudem auf ein Minimum, auch wenn die Vorinstanz - zulässigerweise - eine prima-facie-Würdigung vornahm und Glaubhaftmachung genügen liess. Allein mit dem Streitwert oder dem Arbeitsaufwand in der Sache lässt sich die in Frage stehende Gebühr daher nicht rechtfertigen.
Indem die Vorinstanz im vorliegenden Fall die Gebühr auf Fr. 50'000.-- festgesetzt hat, hat sie den Beschwerdeführern den Zugang zum Gericht und die Ausübung des rechtlichen Gehörs (<ref-law>) in ungebührlicher Weise erschwert. Der angefochtene Entscheid ist daher im Kostenpunkt (Dispositiv Ziffer 2) aufzuheben und die Sache zu neuem Entscheid über die Gerichtsgebühr an die Vorinstanz zurückzuweisen. Die Gerichtsgebühr ist deutlich niedriger festzusetzen.
4. In diesem Sinne ist die Beschwerde teilweise gutzuheissen. Bei der Neufestsetzung der Kosten kann die Vorinstanz auch die Einwendungen der Beschwerdeführer gegen die Auferlegung der vier Portopauschalen überprüfen und diese nötigenfalls berichtigen. Soweit die Beschwerdeführer Aufhebung des angefochtenen Entscheides hinsichtlich der Dispositiv-Ziffer 4 (Parteientschädigung) beantragen, ist die Beschwerde hingegen abzuweisen (vgl. E. 2.3 hiervor).
Bei diesem Verfahrensausgang sind die Verfahrenskosten dem Kanton Zürich und den Beschwerdeführern anteilsmässig, entsprechend den beidseitigen Vermögensinteressen, aufzuerlegen; die Beschwerdeführer haften für ihren Anteil solidarisch (Art. 65 und 66 Abs. 1 Satz 1, Abs. 4 und 5 BGG). Der Kanton Zürich hat den Beschwerdeführern für das bundesgerichtliche Verfahren eine reduzierte Parteientschädigung zu bezahlen (<ref-law>).
Da der kantonalen Instanz keine Verletzung des Anspruchs auf rechtliches Gehör vorgeworfen werden kann (E. 2.2 hiervor), steht auch eine Heilung bei Verletzung des Anspruchs auf rechtliches Gehör - was nach Meinung der Beschwerdeführer volle Befreiung von den Ver fahrenskosten und volle Parteientschädigung im bundesgerichtlichen Verfahren zur Folge haben müsste (vgl. Beschwerde S. 5 f. und S. 10) - nicht in Frage.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Zürich vom 25. Mai 2011 in der Dispositiv-Ziffer 2 aufgehoben. Die Sache wird zur Neuregelung der Gerichtsgebühr und übrigen Kosten (Portopauschalen) im Sinne der Erwägungen an das Verwaltungsgericht zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2. Die Gerichtskosten im Betrag von Fr. 2'400.-- werden dem Kanton Zürich mit Fr. 1'600.-- und den Beschwerdeführern, diesen unter solidarischer Haftung, mit Fr. 800.-- auferlegt.
3. Der Kanton Zürich hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'600.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Gemeinde A._, dem Kantonalen Steueramt Zürich und dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, schriftlich mitgeteilt.
Lausanne, 16. Januar 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Wyssmann