Sachverhalt: A. Die am 7. April 1996 geborene C.X._ wurde im August 2001 frühzeitig eingeschult. Im Anschluss an eine private Begabtenabklärung bei D._ (Fachfrau für Hochbegabungsfragen) verliess sie im Sommer 2004 die öffentliche Primarschule Otelfingen zugunsten einer Privatschule. Das von ihren Eltern A._ und B.X._ in der Folge gestellte Gesuch um Beteiligung an den Kosten für die Privatschulung wies die Gemeinde Otelfingen am 8. April 2004 ab. Diesen Entscheid hat das Verwaltungsgericht des Kantons Zürich am 20. Dezember 2006 kantonal letztinstanzlich geschützt. B. Am 30. Januar 2007 haben A._ und B.X._ hiergegen beim Bundesgericht staatsrechtliche Beschwerde eingereicht mit dem Antrag, den Entscheid des Verwaltungsgerichts aufzuheben und die Sache zu neuem Entscheid an dieses zurückzuweisen. Sie rügen eine Verletzung des Willkürverbots (Art. 9 BV) sowie des Anspruchs auf rechtliches Gehör (Art. 29 Abs. 2 BV). Nach mehrmaliger Fristerstreckung beantragte die Gemeinde Otelfingen am 7. Mai 2007, auf die Beschwerde nicht einzutreten, eventuell die Beschwerde abzuweisen. Die Bildungsdirektion des Kantons Zürich schliesst auf Abweisung der Beschwerde, während das Verwaltungsgericht des Kantons Zürich auf Vernehmlassung verzichtet hat. C. Im Rahmen eines zweiten Schriftenwechsels hielten die Parteien an ihren Anträgen fest. D. Mit Verfügung vom 20. Februar 2007 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts das gestellte Gesuch um aufschiebende Wirkung abgewiesen. 