Sachverhalt:
A. Auf Ersuchen von Y._ bewilligte das Einzelgericht im summarischen Verfahren des Bezirks Meilen mit Befehlen vom 2., 6. und 8. September 2010 gestützt auf <ref-law> für den Betrag von insgesamt Fr. 821'810.-- zuzüglich Zinsen den Arrest der bei X._ zuvor provisorisch gepfändeten Vermögenswerte. Als Forderungsurkunde wurde ein Urteil des Oberlandesgerichts Düsseldorf vom 13. September 2007 bezeichnet. Das Betreibungsamt Stäfa-Hombrechtikon vollzog den Arrest am 10. September 2010. Hinsichtlich der beschlagnahmten Gegenstände übernahm es den Schätzungswert der provisorischen Pfändung in der Höhe von Fr. 242'500.--.
B. Dagegen wandte sich X._ an das Bezirksgericht Meilen, welches seine Arresteinsprache am 14. September 2012 abwies. Die Entscheidgebühr wurde auf Fr. 1'000.-- festgelegt. Das Obergericht des Kantons Zürich wies die Beschwerde von X._ gegen das bezirksgerichtliche Urteil am 3. Dezember 2012 ab. Es setzte die zweitinstanzliche Entscheidgebühr auf Fr. 6'700.-- fest (Dispositivziff. 2) und verrechnete sie mit dem geleisteten Vorschuss (Dispositivziff. 3).
C. X._ ist mit Beschwerde in Zivilsachen vom 9. Januar 2013 an das Bundesgericht gelangt. Der Beschwerdeführer beantragt die Aufhebung des obergerichtlichen Urteils und die Festsetzung der zweitinstanzlichen Entscheidgebühr auf Fr. 3'612.--. Eventualiter sei die Sache an die Vorinstanz zur Neufestsetzung der zweitinstanzlichen Entscheidgebühr anhand des korrekten Streitwertes zurückzuweisen.
Y._ hat am 8. März 2013 (Postaufgabe) eine Beschwerdeantwort eingereicht, ohne einen formellen Antrag zu stellen. Das Obergericht hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. 1.1 Strittig ist die Höhe der Spruchgebühr für einen gerichtlichen Rechtsmittelentscheid in einer betreibungsrechtlichen Summarsache. In der Hauptsache ging es um eine Arresteinsprache, gegen welchen letztinstanzlichen kantonalen Entscheid mit einem Streitwert von weit über Fr. 30'000.-- die Beschwerde in Zivilsachen gegeben ist (Art. 72 Abs. 2 lit. a, Art. 75 Abs. 1, Art. 74 Abs. 1 lit. b BGG). Die dem Rechtsweg in der Hauptsache folgende, auf die Kostenfolgen beschränkte Beschwerde ist daher zulässig.
1.2 Der Entscheid über die Einsprache gegen den Arrestbefehl gilt wie der Arrestentscheid als vorsorgliche Massnahme im Sinne von <ref-law> (<ref-ruling> E. 1.2 S. 234 mit Hinweisen). Damit kann der Beschwerdeführer einzig die Verletzung verfassungsmässiger Rechte geltend machen, wobei das Rügeprinzip gilt (<ref-law>; <ref-ruling> E. 1.4.2 S. 254).
2. Anlass zur vorliegenden Beschwerde gibt die vom Obergericht für die Beurteilung einer Beschwerde gegen einen Arresteinspracheentscheid erhobene Spruchgebühr.
2.1 Das Obergericht ist für die Festsetzung der Spruchgebühr aufgrund der dem angefochtenen Arrest zugrunde liegenden Forderung von einem Streitwert von rund Fr. 821'800.-- ausgegangen. Daraus ergebe sich eine ordentliche Gerichtsgebühr von Fr. 27'150.-- (§ 12 Abs. 1 und 2 i.V.m. § 2 Abs. 1 lit. a und § 4 Abs. 1 Gebührenverordnung des Obergerichts vom 8. September 2010 [GebV OG/ZH]), welche auf rund einen Viertel bzw. auf Fr. 6'700.-- zu kürzen sei, da der Entscheid im summarischen Verfahren ergangen sei (§ 4 Abs. 2 und § 8 Abs. 1 GebV OG/ZH).
2.2 Der Streitwert für das kantonale Verfahren in gerichtlichen Angelegenheiten des Schuldbetreibungs- und Konkursrechts bemisst sich seit dem Inkrafttreten der ZPO nach Bundesrecht (Art. 1 lit. c, Art. 91 ff. ZPO). Die Spruchgebühr in betreibungsrechtlichen Summarsachen (<ref-law>) wird anhand des Streitwertes festgesetzt. Zwar behalten die Kantone die Tarifhoheit für die vor ihren Instanzen anfallenden Prozesskosten (<ref-law>), allerdings nur soweit das Bundesrecht nicht bereits eine Regelung vorsieht, welche dem kantonalen Recht vorgeht (<ref-law>; vgl. dazu allgemein <ref-ruling> E. 3.1 S. 414). Dies ist insbesondere für die Summarsachen des SchKG der Fall, wie das Bundesgericht erst kürzlich entschieden hat (<ref-law>, zur amtl. Publ. bestimmtes Urteil 5A_492/2012 vom 13. März 2013 E. 4.2.4). Demnach richtet sich die Spruchgebühr in diesen Fällen nach Art. 48 bzw. <ref-law>.
2.3 Der Beschwerdeführer beschränkt sich darauf, die Berechnung der Spruchgebühr als willkürlich zu rügen. Hingegen stellt er die vom Obergericht hierzu angewandte GebV OG/ZH, mithin die Anwendung kantonalen Rechts, nicht in Frage. Zudem stellt er den Antrag, die Spruchgebühr auf Fr. 3'612.-- festzusetzen. Daran ist das Bundesgericht gebunden (<ref-law>). Damit kann es vorliegend einzig anhand der konkreten (Willkür-) Rügen prüfen, ob die Höhe der Spruchgebühr im Ergebnis unhaltbar ist (vgl. zum Willkürbegriff <ref-ruling> E. 4.1 S. 133).
2.4 Der Beschwerdeführer stellt nicht in Frage, dass die Spruchgebühr in Arrestsachen anhand des Streitwertes festgelegt wird (<ref-law>). Hingegen wehrt er sich im Wesentlichen gegen die Festsetzung des Streitwertes anhand der Forderung, für welche der Arrest gelegt worden ist. Dafür gebe es keinen sachlichen Grund, womit Willkür vorliege.
2.4.1 Die kantonalrechtliche Praxis zur Festsetzung des Streitwertes in Arrestsachen war nicht einheitlich. Die Frage wird auch in der Lehre zu <ref-law> unterschiedlich beantwortet. Es gibt Autoren, welche von der zu sichernden Forderung ausgehen (VOCK/MÜLLER, SchKG-Klagen nach der Schweizerischen ZPO, 2012, S. 299), während andere auf den Schätzwert des Arrestobjektes abstellen, da nur der Bestand des Arrestbeschlags Streitgegenstand bildet (STERCHI, in: Berner Kommentar, ZPO, Bd. I, 2012, N. 20a zu <ref-law>; MEIER, Schweizerisches Zivilprozessrecht, 2010, S. 480, Fn. 869, sowie bereits POUDRET, Commentaire LOJ, Bd. I, 1990, Ziff. 9.9.9 zu Art. 36 OG, S. 291). Das Bundesgericht hat sich bisher nur vereinzelt zur Bestimmung des Streitwertes geäussert. So hat es auf den Wert des Arrestobjektes abgestellt in einem Fall, wo der Dritte sich gegen die Arresteinsprache zur Wehr gesetzt hat (Urteil 5A_789/2010 vom 29. Juni 2011 E. 1.2). In anderen Fällen konnte es diese Frage offen lassen, da sich die Bezugnahme auf die Arrestforderung im Ergebnis nicht als unhaltbar erwies (zur amtl. Publ. bestimmtes Urteil 5A_492/2012 vom 13. März 2013 E. 4.3.2).
2.4.2 Nach Ansicht des Beschwerdeführers muss vom Wert der verarrestierten Gegenstände ausgegangen werden, um ein unhaltbares Ergebnis zu vermeiden. Dies gelte insbesondere, wenn deren Schätzungswert (Fr. 242'500.--) - wie im vorliegenden Fall - nur rund einen Drittel der Arrestforderung decken (Fr. 821'800.--). Diese Sicht auf das Auseinanderfallen der beiden Ansätze führt isoliert betrachtet keinesfalls bereits zum Schluss, es sei willkürlich, vom höheren Betrag auszugehen. Zwar trifft auch das Vorbringen des Beschwerdeführers zu, dass über die vom Obergericht für die Festsetzung des Streitwertes massgebliche Forderung bereits seit Jahren rechtskräftig entschieden worden sei, weshalb sie im konkreten Verfahren nie Anlass zu Differenzen gegeben habe. In diese Richtung weisen auch die Lehrmeinungen, die auf den Wert des Arrestgegenstandes hinweisen (vgl. E. 2.4.1). Entscheidend ist jedoch im vorliegenden Fall, dass das Betreibungsamt beim Vollzug des Arrestes für den Wert der beschlagnahmten Gegenstände auf die vorangegangene provisorische Pfändung und insbesondere auf die damals vorgenommene Schätzung Bezug nahm. Ist der Wert der Arrestgegenstände - wie vorliegend - bekannt, so ist es nicht sachgerecht, bei der Festlegung des Streitwertes für die Anfechtung des Arrestes nicht von diesem Betrag, sondern von der Arrestforderung auszugehen. Im Hinblick auf die Bemessung des Streitwertes sind die Fälle anders zu beurteilen, bei denen der Wert des Arrestgegenstandes im Zeitpunkt der Anfechtung des Arrestes gerade nicht bekannt ist. Eine solche Situation ist beispielsweise bei der Verarrestierung von Bankguthaben gegeben. Die Bank muss nämlich erst nach rechtskräftiger Erledigung der Arresteinsprache über deren Höhe Auskunft geben (vgl. dazu <ref-ruling> E. 2 S. 292), womit sich in einem solchen Fall der Wert des Arrestgegenstandes (mangels Anhaltspunkte) nicht als taugliches Kriterium für die Berechnung des Streitwertes eignet.
2.5 Da sich der vom Obergericht angenommene Streitwert als willkürlich erweist, erübrigt sich die Behandlung der weiteren Rügen. Nicht angefochten ist zudem die Anwendung der kantonalen Verordnung, soweit es um die Herabsetzung des Grundtarifs geht. Ausgehend vom Schätzwert der Arrestgegenstände (Fr. 242'500.--) und in Bindung an den Antrag des Beschwerdeführers ist die Spruchgebühr der Vorinstanz auf Fr. 3'612.- festzusetzen.
3. Nach dem Gesagten ist der Beschwerde Erfolg beschieden. Ausgangsgemäss trägt der Kanton Zürich, der in seinen Vermögensinteressen betroffen ist, die Kosten (<ref-law>). Zudem hat er dem Beschwerdeführer für das Verfahren vor Bundesgericht eine Parteientschädigung zu leisten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird gutgeheissen und die Ziff. 2 und 3 des Urteils des Obergerichts des Kantons Zürich vom 3. Dezember 2012 werden aufgehoben. Die zweitinstanzliche Spruchgebühr wird auf Fr. 3'612.-- festgesetzt.
2. Die Gerichtskosten von Fr. 1'000.-- werden dem Kanton Zürich auferlegt.
3. Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 15. April 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Levante