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 (<ref-law>) sowie des Anspruchs auf rechtliches Gehör (<ref-law>).
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.

Erwägungen:
1. 1.1 Auf das vorliegende Verfahren findet noch das bis Ende 2006 geltende Bundesgesetz vom 16. Dezember 1943 über die Organisation der Bundesrechtspflege (OG) Anwendung (vgl. Art. 132 Abs. 1 des am 1. Januar 2007 in Kraft getretenen Bundesgesetzes vom 17. Juni 2005 über das Bundesgericht [BGG; SR 173.110]).
1.2 Angefochten ist ein kantonal letztinstanzlicher Endentscheid, der sich auf kantonales Recht stützt und gegen den auf Bundesebene deshalb nur die staatsrechtliche Beschwerde offen steht (Art. 86 Abs. 1 und Art. 87 in Verbindung mit Art. 84 Abs. 2 OG). Es ist unstreitig, dass das kantonale Schulrecht bei Erfüllen der gesetzlichen Voraussetzungen einen Anspruch auf geeignete Sonderschulung gewährt, so dass die Beschwerdeführer als Eltern des betroffenen Schulkindes in rechtlich geschützten Interessen berührt und deshalb zur staatsrechtlichen Beschwerde legitimiert sind (vgl. Art. 88 OG; <ref-ruling> E. 1 S. 219; <ref-ruling> E. 3b S. 85).
1.3 Die staatsrechtliche Beschwerde muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Entscheid verletzt worden sind (Art. 90 Abs. 1 lit. b OG). Das Bundesgericht untersucht nicht von Amtes wegen, ob ein kantonaler Hoheitsakt verfassungsmässig ist, sondern prüft nur rechtsgenügend vorgebrachte, klar erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 2 S. 3 f.; <ref-ruling> E. 1d S. 201, mit Hinweisen). Wird eine Verletzung des Willkürverbots (<ref-law>) geltend gemacht, genügt es nicht, wenn der Beschwerdeführer bloss den angefochtenen Entscheid kritisiert, wie er dies in einem appellatorischen Verfahren tun könnte, bei dem die Rechtsmittelinstanz die Rechtsanwendung frei überprüfen kann. Er muss deutlich dartun, welche Vorschriften oder allgemein anerkannten Rechtsgrundsätze die kantonalen Behörden in einer gegen <ref-law> verstossenden Weise verletzt haben sollen (<ref-ruling> E. 4b S. 12). Die Gemeinde Otelfingen macht geltend, die Beschwerdeschrift enthalte keinerlei diesen Begründungsanforderungen genügenden Vorbringen, weshalb auf die staatsrechtliche Beschwerde nicht einzutreten sei. Ihr ist insoweit zuzustimmen, dass die Ausführungen der Beschwerdeführer zumindest über weite Strecken (vgl. insb. E. 5.2) rein appellatorischer Natur sind. Auf die entsprechenden Vorbringen ist nach dem Gesagten nicht einzugehen.
2. Im angefochtenen Entscheid hat das Verwaltungsgericht ausgeführt, auf hochbegabte Schüler sei die kantonale Regelung über die Sonderschulung körperlich oder geistig gebrechlicher bzw. schwer erziehbarer Kinder analog anwendbar. Gemäss dieser sollen Kinder möglichst den Unterricht in der Regelklasse besuchen und nur dann einer Sonderschule zugewiesen werden, wenn sie trotz Stütz- und Fördermassnahmen in der Normalklasse nicht ihren intellektuellen Fähigkeiten entsprechend gefördert werden können. Eine Sonderschulung in einer Privatschule komme nur als "ultima ratio" in Betracht und ein dahingehender Anspruch sei nur "in speziell gelagerten Fällen" anzuerkennen. Die Notwendigkeit einer Privatschulung bzw. das Ungenügen des Angebots der öffentlichen Schule sei zum Zeitpunkt der Einschulung in eine Privatschule zu beurteilen, weshalb vorliegend die Situation im Frühjahr 2004 massgebend sei. Die Voraussetzungen für eine Privatschulung seien im Fall von C._ nicht gegeben gewesen, zumal gemäss den Untersuchungen des schulpsychologischen Abklärungsdiensts das in der Primarschule Otelfingen ab Sommer 2004 neu angebotene "Hochbegabten-Coaching" für C._ geeignet gewesen wäre.
3. 3.1 Die Beschwerdeführer rügen zunächst eine Verletzung des Anspruchs auf rechtliches Gehör (<ref-law>; vgl. <ref-ruling> E. 3.2 S. 236; <ref-ruling> E. 2.2 S. 504 f.), weil das Verwaltungsgericht das von ihnen beantragte Obergutachten nicht eingeholt habe. Hierzu wäre es ihrer Auffassung nach verpflichtet gewesen, weil hinsichtlich der Frage, ob die schuleigenen Förderungsmassnahmen für C._ geeignet waren, zwei unterschiedliche Expertenmeinungen vorlägen. Während der schulpsychologische Beratungsdienst des Bezirks Dielsdorf empfehle, das Hochbegabten-Coaching der Primarschule Otelfingen auszuprobieren, bevor zu einer Privatschulung geschritten werde, halte die von ihnen konsultierte Fachfrau für Hochbegabungsfragen, D._, das fragliche Angebot der öffentlichen Schule für ungenügend.
3.2 Es trifft zu, dass D._ das schuleigene Hochbegabten-Coaching zumindest in ihren vom 30. Januar 2006 datierenden "Erläuterungen zum Kurzbericht" als für C._ ungeeignet bezeichnet hat. Das Verwaltungsgericht hat diese Auffassung jedoch verworfen, weil sie nicht auf tatsächlichen Erfahrungen beruht bzw. weil das Hochbegabten-Coaching nicht zum Vornherein "als untaugliche Massnahme bezeichnet werden" könne. Im Rahmen der vorzunehmenden (freien) Beweiswürdigung war das Verwaltungsgericht hierzu ohne weiteres berechtigt, muss doch eine Gerichtsbehörde bei Vorliegen von sich widersprechender Expertenmeinungen regelmässig selber entscheiden, welcher der beiden Auffassungen im konkreten Fall zu folgen ist. Von Verfassungs wegen ist die Einholung eines Obergutachtens nur dann geboten, wenn der Richter angesichts der unterschiedlichen Expertenmeinungen zu keiner eigenen Überzeugung kommt. Schliesst er sich demgegenüber der einen oder der anderen Auffassung an, so kann sich im Anschluss an diesen Entscheid nur noch die Frage stellen, ob die entsprechende Beweiswürdigung verfassungskonform ist.
4. Die Beschwerdeführer bringen weiter vor, das Verwaltungsgericht habe für seinen Entscheid allein auf das Gutachten des schulpsychologischen Beratungsdiensts abgestellt und sich mit dem Inhalt ihres "Privatgutachtens" überhaupt nicht auseinandergesetzt; diese einseitige Berücksichtigung von Beweisen verletze das Willkürverbot (vgl. <ref-ruling> E. 2a S. 41). Mit dieser Argumentation übersehen die Beschwerdeführer, dass es das Verwaltungsgericht klar und deutlich abgelehnt hat, die Tauglichkeit der Hochbegabtenförderung der öffentlichen Schule generell und ohne konkrete Erfahrungen zu verneinen. Mit Blick darauf, dass das kantonale Recht hochbegabten Kindern zwar einen Anspruch auf besondere Förderungsmassnahmen, nicht aber auf die bestmögliche Schulung gewährt und deshalb eine mit öffentlichen Mitteln unterstützte Privatschulung nur als "ultima ratio" zulässt, leuchtet dies ein. Zudem handelt es sich bei den "Erläuterungen zum Kurzbericht" von D._ nicht um ein eigentliches Gutachten, sondern bloss um ein kurzes, aus einigen wenigen Sätzen bestehendes Schreiben. Eine eingehendere Auseinandersetzung mit dessen Inhalt war - obschon mit Blick auf die allgemeine Begründungspflicht von <ref-law> an sich wünschenswert - verfassungsrechtlich nicht zwingend erforderlich. Diesbezüglich ist weiter zu beachten, dass die Einschätzung von D._ auf der falschen Annahme beruht, C._ wäre in der öffentlichen Schule bloss in den Genuss einer einzigen Förderungslektion mit einer besonderen Lehrkraft für Hochbegabte gekommen, während es in Tat und Wahrheit immerhin deren drei gewesen wären. Dieser Mangel reduziert die Überzeugungskraft ihrer Beurteilung nicht unwesentlich; bereits deswegen kann von einer Verletzung des Willkürverbots keine Rede sein, wenn das Verwaltungsgericht der Empfehlung des schulpsychologischen Beratungsdiensts folgend eine vorgängige Teilnahme an der schuleigenen Hochbegabtenförderung für angebracht erachtet hat.
5. Schliesslich rügen die Beschwerdeführer auch eine willkürliche Handhabung von § 12 des Zürcher Volksschulgesetzes.
5.1 Gemäss dieser Bestimmung sind bildungsfähige, aber körperlich oder geistig gebrechliche sowie schwer erziehbare oder sittlich gefährdete Kinder, die dem Unterricht in Normalklassen nicht zu folgen vermögen oder ihn wesentlich behindern, durch die Schulpflege (auf Grund eines Zeugnisses des Schularztes und nach Anhören der Eltern) Sonderklassen zuzuweisen (Abs. 1). Kinder, für die auch ein Unterricht in Sonderklassen nicht in Frage kommt, sind auf Grund eines Zeugnisses des Schularztes einer Sonderschulung zuzuführen. Für die Dauer der Schulpflicht haben diese Kinder Anspruch auf eine ihren Gebrechen und ihrer Bildungsfähigkeit besonders angepasste Schulung und Erziehung (Abs. 2). Weil das Volksschulgesetz für Kinder, die besonders leistungsfähig oder besonders begabt sind, keine besonderen Massnahmen vorsieht, wendet das Verwaltungsgericht § 12 des Volksschulgesetzes analog auf solche Kinder an (vgl. E. 2).
5.2 Die Beschwerdeführer stellen diese Auslegung von § 12 des Zürcher Volksschulgesetzes nicht in Frage. Weiter akzeptieren sie auch ausdrücklich, dass für Hochbegabte eine Sonderschulung in einer Privatschule nur als "ultima ratio" in Betracht fällt (vgl. hierzu auch Urteil 2P.216/2002 vom 5. Februar 2003, E. 5.4). Sie machen einzig geltend, dass der Unterforderung von C._ nur durch einen Übertritt in die Privatschule habe begegnet werden können, wobei sie diesbezüglich auf das "aussagekräftigere Gutachten" von D._ verweisen. Mit diesen Ausführungen rügen sie im Ergebnis aber nicht die Anwendung des kantonalen Gesetzesrechts, sondern beanstanden vielmehr erneut die vorgenommene Beweiswürdigung. Ihre diesbezüglichen Vorbringen sind jedoch ohnehin rein appellatorischer Natur, weshalb auf sie so oder anders nicht einzugehen ist (vgl. E. 1.3).
6. Nach dem Gesagten ist die staatsrechtliche Beschwerde unbegründet, soweit auf sie einzutreten ist.
Bei diesem Verfahrensausgang werden die Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 und Abs. 7 in Verbindung mit Art. 153 und Art. 153a OG). Als öffentlich-rechtliche Körperschaft hätte die obsiegende Gemeinde Otelfingen an sich keinen Anspruch auf Parteientschädigung (Art. 159 Abs. 2 OG analog). In Anwendung der Ausnahmeregelung, welche die Rechtsprechung unter der Herrschaft des Bundesgesetz vom 16. Dezember 1943 über die Organisation der Bundesrechtspflege zugunsten kleinerer Gemeinwesen ohne eigenen Rechtsdienst begründet hat (vgl. <ref-ruling> E. 7 S. 202; Urteil 2P.458/1995 vom 13. Mai 1997, E. 6), ist der Beschwerdegegnerin vorliegend dennoch eine angemessene Entschädigung für den mit dem bundesgerichtlichen Verfahren verbundenen anwaltlichen Aufwand zuzusprechen.

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 5'000.-- wird den Beschwerdeführern unter Solidarhaft auferlegt.
3. Für das bundesgerichtliche Verfahren haben die Beschwerdeführer, unter Solidarhaft, die Beschwerdegegnerin mit Fr. 5'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien sowie der Bildungsdirektion und dem Verwaltungsgericht (4. Abteilung, 4. Kammer) des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 5. Februar 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Häberli