Sachverhalt: A. Das Amt für Landschaft und Natur des Kantons Zürich (nachfolgend: Amt für Landschaft und Natur) stellte am 25. August 2008 auf Gesuch von A._, B._, C._, D._, der E._AG und der F._AG fest, dass Kiesabbaurechte, welche zu Gunsten der F._AG bzw. der E._AG und zu Lasten der in der Gemeinde X._ liegenden Grundstücke mit den Kataster-Nummern xxxx, yyyy und zzzz errichtet werden, keiner Bewilligungspflicht nach BGBB unterliegen. Die Verfügung wurde der H._ AG - auf deren Gesuch hin - mit Schreiben vom 24. September 2008 ebenfalls eröffnet. B. Am 27. Oktober 2008 gelangte die H._ AG unter dem Titel "Rekurs (ev. Aufsichtsbeschwerde) " an den Regierungsrat des Kantons Zürich (nachfolgend: Regierungsrat) und beantragte, die Verfügung vom 25. August 2008 aufzuheben und festzustellen, dass der Eintrag von Dienstbarkeiten betreffend Kiesabbau bewilligungspflichtig sei. Sodann sei festzustellen, dass die Bewilligung des Eintrags dieser Dienstbarkeiten im Grundbuch (Erwerbsbewilligung) vorliegend zu verweigern sei; eventuell sei die entsprechende Bewilligung zu verweigern. Der Regierungsrat trat mit Beschluss vom 13. Juni 2012 wegen fehlender Legitimation der H._ AG auf den Rekurs nicht ein, hob indessen die Verfügung vom 25. August 2008 aufsichtsrechtlich auf. Er stellte fest, dass der Eintrag der fraglichen Dienstbarkeiten bewilligungspflichtig sei, und wies das Amt für Landschaft und Natur an, einen Entscheid über die Erteilung der Bewilligung zu fällen. Gegen den Regierungsratsbeschluss vom 13. Juni 2012 erhoben A._, B._, C._, D._, die E._ AG und die F._ AG am 20. August 2012 Beschwerde beim Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht) mit dem Begehren, die aufsichtsrechtlichen Anordnungen aufzuheben bzw. die Verfügung vom 25. August 2008 zu bestätigen. Mit Urteil vom 21. November 2012 wies das Verwaltungsgericht die Beschwerde ab. C. A._, B._, C._, D._, die E._AG und die F._AG erheben am 14. Januar 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit dem Antrag, das angefochtene Urteil aufzuheben und die Verfügung des Amts für Landschaft und Natur vom 25. August 2008 zu bestätigen. Das Verwaltungsgericht und der Regierungsrat schliessen auf Abweisung der Beschwerde. Das Amt für Landschaft und Natur beantragt die Gutheissung der Beschwerde; im Fall der Abweisung werde das Bundesgericht ersucht, konkrete Ausführungen zur Frage, in welcher Höhe eine Entschädigung als Abgeltung für den Eintrag einer solchen Dienstbarkeit zulässig sei und zur Frage des Kreises möglicher Dienstbarkeitsberechtigter zu machen. Das Bundesamt für Justiz lässt sich vernehmen, ohne einen ausdrücklichen Antrag zu stellen.