Sachverhalt: A. Y._ wurde im Jahr 1992 geboren. Er besuchte zuletzt ein Gymnasium in Deutschland, ehe er zu Beginn des Schuljahrs 2008/2009 in die vierte Klasse des Gymnasiums A._ in Basel eintrat. Aufgrund nicht erfüllter Promotionsvoraussetzungen verfügte das Gymnasium A._ die Remotion, worauf Y._ im Schuljahr 2009/2010 die vierte Gymnasialklasse wiederholte. Wenngleich die Leistungen keine Promotion zugelassen hätten, wurde ihm im Sinne einer Ausnahme ermöglicht, in die fünfte, letzte Gymnasialklasse des Schuljahres 2010/2011 überzutreten. Begründet wurde dies im Wesentlichen damit, dass der Schüler aus dem Ausland zugezogen sei und über ein Defizit im Bereich des Französisch verfüge. Die ausnahmsweise Promotion wurde an die Bedingung geknüpft, dass die eigens angesetzte ausserordentliche Probezeit, ein Semester, erfolgreich bestanden werde. Y._ schloss das erste Semester des fünften Gymnasialjahres mit vier ungenügenden Noten ab ("Biologie und Chemie", "Französisch", "Mathematik", "Wirtschaft und Recht"). Mit Blick darauf und auf die fehlende Möglichkeit einer Repetition des zweiten Semesters der vierten Gymnasialklasse ordnete das Gymnasium A._ die Wegweisung von der Schule an, worauf Y._ die Schule am 21. Januar 2011 verliess. B. Die Eltern des Schülers bemühten sich in der Folge um den Eintritt ihres Sohnes in das Gymnasium B._, was dessen Rektor zunächst zustimmend beantwortete (Aufnahme in die vierte Gymnasialklasse), letztlich aber am 23. Februar 2011 mit Blick auf die Vorgeschichte verwarf. Dem vorübergehenden Besuch des Unterrichts in der vierten Klasse, freilich als Hospitant bis zum Übertritt in eine andere Ausbildung, stehe, so der Rektor, aber nichts entgegen. C. X._, der Vater des Schülers, gelangte am 28. Februar 2011 an das Erziehungsdepartement des Kantons Basel-Stadt und beantragte die Zulassung seines Sohnes zur Repetition der fünften Gymnasialklasse, dies ab Sommer 2011 und nunmehr am Gymnasium B._. Der Leiter der Dienststelle "Weiterführende Schulen" des Erziehungsdepartements bestätigte in seiner Verfügung vom 29. Juni 2011 den Standpunkt, welchen die Rektorin des Gymnasiums A._ eingenommen hatte. Danach sei eine weitere Repetition nicht vorgesehen, sodass keine Möglichkeit bestehe, die Ausbildung fortzusetzen und an einem staatlichen oder privaten Gymnasium im Kanton Basel-Stadt zur Maturitätsprüfung zu gelangen. Eine dagegen gerichtete Beschwerde vom 25. Juli 2011 wies das Erziehungsdepartement des Kantons Basel-Stadt am 28. September 2011 ab, ebenso wie das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, das am 15. Februar 2012 den Rekurs vom 4. Oktober/30. November 2011 beurteilte. D. Gegen dieses Urteil erheben X._ (Beschwerdeführer 1) und Y._ (Beschwerdeführer 2) mit Eingabe vom 23. März 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, das angefochtene Urteil des Appellationsgerichts des Kantons Basel-Stadt sei aufzuheben, und es sei das Erziehungsdepartement des Kantons Basel-Stadt anzuweisen, den Beschwerdeführer 2 "zur fünften Klasse bzw. zu den Maturitätsprüfungen im Gymnasium B._ zuzulassen". Überdies sei der Beschwerde die aufschiebende Wirkung zuzuerkennen. Das Appellationsgericht und das Erziehungsdepartement beantragen die Abweisung der Beschwerde.