Sachverhalt: A. Die neunjährige Z._ und die siebenjährige W._ besuchten im August 2008 die Primarschule in Basel. Sie blieben dem obligatorischen Schwimmunterricht fern. Auch nach Gesprächen der Schulleitung mit den Eltern, X._ und Y._, besuchten die beiden Kinder den Schwimmunterricht nicht. Am 28. Juli 2010 büsste das Erziehungsdepartement des Kantons Basel-Stadt die beiden Eltern wegen wiederholter Verletzung der elterlichen Pflichten gemäss Schulgesetzgebung je mit Fr. 700.-- (pro Tochter mit je Fr. 350.--). Das Appellationsgericht des Kantons Basel-Stadt wies den dagegen erhobenen Rekurs der Eltern am 30. Mai 2011 ab. B. X._ und Y._ beantragen dem Bundesgericht mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, den Entscheid des Appellationsgerichts vom 30. Mai 2011 aufzuheben und festzustellen, dass die Ordnungsbusse des Erziehungsdepartements einen unzulässigen Eingriff in ihre Glaubens- und Gewissensfreiheit darstelle. Ausserdem verlangen sie, dass ihrer Vertreterin für das Verfahren vor Appellationsgericht ein Honorar von insgesamt Fr. 4'933.40 zugesprochen werde. Das Erziehungsdepartement und das Verwaltungsgericht des Kantons Basel-Stadt ersuchen um Abweisung der Beschwerde. Die Beschwerdeführer haben am 24. Oktober 2011 zu den Vernehmlassungen des Beschwerdegegners und der Vorinstanz Stellung genommen. 