Sachverhalt: A. X._ und Y._ sind Eigentümer des Grundstücks Kat.-Nr. 11898 in A._ (Gemeinde B._). Auf der Parzelle steht ein Einfamilienhaus, das sie selber bewohnen. Am 30. März/6. April 2009 beschloss die Gemeindeversammlung von B._ eine Teilrevision der kommunalen Nutzungsplanung. Nebst fünf weiteren Gebieten wurde das Gebiet Gebiet D._ mit der Liegenschaft von X._ und Y._ von der Wohnzone W2/1,9 in eine Wohnzone W2/1,6 abgezont. Dagegen führten X._ und Y._ erfolglos Rekurs bei der Baurekurskommission II. B. Am 18. Dezember 2009 stellten X._ und Y._ beim Gemeinderat von B._ ein Gesuch um Ausrichtung einer Entschädigung aus materieller Enteignung. Der Gemeinderat wies das Entschädigungsbegehren mit Beschluss vom 23. Februar 2010 ab und beantragte beim Statthalteramt des Bezirks C._ die Einleitung des Schätzungsverfahrens. Er stellte sich auf den Standpunkt, dass die Abzonung der Liegenschaft keinen enteignungsähnlichen Eingriff darstelle. X._ und Y._ beantragten, es sei das Vorliegen einer materiellen Enteignung festzustellen und ihnen eine Entschädigung von Fr. 925'000.-- zuzusprechen. Mit Entscheid vom 1. Dezember 2010 stellte die Schätzungskommission Kreis II des Kantons Zürich fest, es liege kein entschädigungspflichtiger Eingriff vor. Hiergegen erhoben X._ und Y._ Rekurs beim Verwaltungsgericht des Kantons Zürich. Dieses gelangte zum selben Ergebnis wie die Schätzungskommission und wies den Rekurs mit Urteil vom 26. Mai 2011 ab. C. Mit Eingabe vom 23. August 2011 führen X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen die Aufhebung des verwaltungsgerichtlichen Urteils, die Feststellung des Vorliegens einer materiellen Enteignung und die Zusprechung einer Entschädigung von Fr. 925'000.-- zu Lasten der Gemeinde B._. Die Gemeinde B._ beantragt mit Beschwerdeantwort vom 12. Oktober 2011 im Hauptstandpunkt die Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich schliesst ebenfalls auf Abweisung der Beschwerde, soweit darauf einzutreten sei (Vernehmlassung vom 30. August 2011). Das Bundesamt für Raumentwicklung hat auf eine Stellungnahme verzichtet (Eingabe vom 16. November 2011). Die Beschwerdeführer halten in Schlussbemerkungen vom 9. Dezember 2011 an ihren Begehren fest.