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.

Erwägungen:
1. 1.1 Der gestützt auf das Schulgesetz vom 4. April 1929 des Kantons Basel-Stadt (SchulG/BS) ergangene, kantonal letztinstanzliche Entscheid der Vorinstanz kann mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht angefochten werden (Art. 82 lit. a, Art. 86 Abs. 1 lit. d BGG). Eine Ausnahme liegt nicht vor. Auf die frist- und formgerechte Beschwerde ist einzutreten.
1.2 Die Beschwerdeführer beantragen neben der Aufhebung des angefochtenen Entscheids, es sei festzustellen, dass die verhängten Ordnungsbussen ihre Glaubens- und Gewissensfreiheit verletzten. Es handelt sich dabei offensichtlich um eine ungenaue Ausdrucksweise. Ziel der Beschwerdeführer ist es, von der Pflicht zur Zahlung der Ordnungsbussen befreit zu werden. Ihr Feststellungsbegehren ist in diesem Sinn zu verstehen.
1.3 Soweit die Beschwerdeführer ebenfalls verlangen, ihrer Rechtsvertreterin sei für das vorinstanzliche Verfahren eine Entschädigung von Fr. 4'933.40 zuzusprechen, ist auf ihr Rechtsmittel nicht einzutreten. Denn der Honoraranspruch steht der amtlichen Rechtsbeiständin selber zu und nicht den verbeiständeten Parteien. Die Rechtsvertreterin darf von den Letzteren neben dem vom Staat zugesprochenen auch kein zusätzliches Honorar verlangen. Der verbeiständeten Partei fehlt daher grundsätzlich die Legitimation, sich gegen eine zu tiefe Entschädigung ihrer Rechtsvertreterin zur Wehr zu setzen; die Parteistellung kommt nur der Letzteren selber zu (<ref-ruling> E. 2 S. 363 f.). Besondere Umstände, die ein Abgehen von dieser Regel rechtfertigen könnten (vgl. Urteil 5A.415/2011 vom 25. Juli 2011, E. 1.2), tun die Beschwerdeführer nicht dar und sind nicht ersichtlich.
2. 2.1 Streitgegenstand bildet die Verfassungsmässigkeit der den Beschwerdeführern auferlegten Ordnungsbussen von je Fr. 700.--. Die Vorinstanz stützt diese Sanktionen auf § 91 Abs. 8 lit. b und Abs. 9 SchulG/BS. Danach können Erziehungsberechtigte, die ihre Kinder wiederholt wissentlich von der Schule fernbleiben lassen, mit einer Ordnungsbusse bis Fr. 1'000.-- belegt werden.
2.2 Die Beschwerdeführer stellen die grundsätzliche Anwendbarkeit dieser Regelung nicht in Frage, ebenso wenig die Höhe der ausgesprochenen Ordnungsbussen. Sie machen allein geltend, die Glaubens- und Gewissensfreiheit gewähre ihnen ein Recht auf Dispensation ihrer beiden Töchter vom gemischtgeschlechtlichen Schwimmunterricht. Sie seien deshalb nicht verpflichtet gewesen, ihre Töchter in diesen Unterricht zu schicken und hätten demzufolge ihre Pflichten als Eltern nicht verletzt, weshalb ihnen keine Ordnungsbusse auferlegt werden dürfe.
2.3 Die Beschwerdeführer bekennen sich zu einem strengen muslimischen Glauben. Dieser verbiete einen gemeinsamen Schwimmunterricht für Knaben und Mädchen. Zwar verlange der Koran vom Wortlaut her die Bedeckung des weiblichen Körpers erst ab der Zeit der Geschlechtsreife; doch untersage eine islamisch orientierte Schamerziehung einen gemischtgeschlechtlichen Schwimmunterricht schon vorher, um die Kinder auf die späteren Vorschriften vorzubereiten.
2.4 Die Vorinstanz anerkennt, dass die Befolgung der erwähnten Glaubensregel nach der bundesgerichtlichen Rechtsprechung (<ref-ruling> E. 4 S. 82 ff.) den Schutz der Glaubens- und Gewissensfreiheit geniesst. Umgekehrt räumen auch die Beschwerdeführer selber ein, dass das umstrittene Schulobligatorium nicht in den Kernbereich des erwähnten Grundrechts eingreift. Zu prüfen ist daher allein, ob das Obligatorium die Voraussetzungen, die gemäss Art. 36 Abs. 1-3 BV für Grundrechtseinschränkungen gelten, erfüllt.
2.4 Die Vorinstanz anerkennt, dass die Befolgung der erwähnten Glaubensregel nach der bundesgerichtlichen Rechtsprechung (<ref-ruling> E. 4 S. 82 ff.) den Schutz der Glaubens- und Gewissensfreiheit geniesst. Umgekehrt räumen auch die Beschwerdeführer selber ein, dass das umstrittene Schulobligatorium nicht in den Kernbereich des erwähnten Grundrechts eingreift. Zu prüfen ist daher allein, ob das Obligatorium die Voraussetzungen, die gemäss Art. 36 Abs. 1-3 BV für Grundrechtseinschränkungen gelten, erfüllt.
2.5 2.5.1 Nach Auffassung der Beschwerdeführer ergibt sich die Pflicht, ihre Töchter in den gemischtgeschlechtlichen Schwimmunterricht zu schicken, nicht zwingend aus einem Rechtssatz. Es fehle daher die nach Art. 36 Abs. 1 BV bei einem Grundrechtseingriff erforderliche gesetzliche Grundlage.
2.5.2 Nach § 22 SchulG/BS zählt das Turnen zu den obligatorischen Unterrichtsfächern der Primarschule. Weiter bestimmt § 139 Abs. 1 SchulG/BS, dass der Übung und Erziehung des Körpers im Rahmen des Unterrichtsplans wöchentlich mindestens drei Stunden zu widmen sind. Mädchen und Knaben sind in Primarschulen in der Regel gemeinsam zu unterrichten (§ 17 SchulG/BS). Die nähere Ausgestaltung des obligatorischen Unterrichts - insbesondere die Fächer und die Zahl der darauf entfallenden Stunden - ergeben sich aus dem Lehrplan (§ 68 SchulG/BS). Letzterer sieht in Ziff. 9.2.4 das Schwimmen als Teil des obligatorischen Turn- und Sportunterrichts vor.
Schüler können vom Unterricht oder von einzelnen Unterrichtsfächern oder -stunden dispensiert werden; darüber entscheidet die Schulleitung auf Antrag des Lehrpersonenteams oder auf Antrag der Erziehungsberechtigten (§ 66 Abs. 5 und 6 SchulG/BS). §§ 34 ff. der kantonalen Schulordnung vom 1. Oktober 1975 regeln die Einzelheiten der Dispensation. Das Erziehungsdepartement des Kantons Basel-Stadt hat ausserdem zum Umgang mit religiösen Fragen an der Schule im September 2007 eine Handreichung herausgegeben. Nach deren Ziff. 5.1 können Dispensationen vom Schwimmunterricht nur Schülerinnen und Schülern erteilt werden, die Geschlechtsreife erlangt haben. Ab dem sechsten Schuljahr wird indessen der Schwimm- und Sportunterricht in Basel-Stadt ohnehin in der Regel geschlechtergetrennt durchgeführt (Ziff. 5.3 der Handreichung).
2.5.3 Die kantonalen Instanzen sehen in den genannten Bestimmungen eine ausreichende gesetzliche Grundlage, um von den Beschwerdeführern den Besuch des Schwimmunterrichts ihrer Töchter zu verlangen. Dies entspricht der bundesgerichtlichen Rechtsprechung, die eine formellgesetzliche Grundlage nur für die Schulpflicht selber und die Grundzüge der Ausgestaltung des Schulunterrichts verlangt, für die Bestimmung der einzelnen obligatorischen Unterrichtsfächer bzw. deren Ausgestaltung dagegen den öffentlich zugänglichen Lehrplan als ausreichende Grundlage erachtet (<ref-ruling> E. 6 S. 85 f.). Der Einwand der Beschwerdeführer, der erwähnten Handreichung komme überhaupt kein rechtsverbindlicher Charakter zu, ist nicht ausschlaggebend. Denn der obligatorische Charakter des Schwimmunterrichts ergibt sich bereits aus den angeführten gesetzlichen Bestimmungen und dem Lehrplan; die Handreichung ist lediglich eine Anleitung zur Handhabung des Ermessens bei der Erteilung von Dispensationen. Ebenso wenig ist es mit Blick auf die gesetzliche Grundlage von Bedeutung, dass möglicherweise nicht in allen Schulhäusern Basels Schwimmunterricht erteilt und das im Lehrplan ebenfalls vorgesehene Eislaufen überhaupt nicht unterrichtet wird, wie dies die Beschwerdeführer behaupten. Diese Umstände ändern nichts an der rechtlichen Verankerung des umstrittenen Obligatoriums.
Die Rüge, die fragliche Einschränkung der Glaubens- und Gewissensfreiheit entbehre der erforderlichen gesetzlichen Grundlage, erweist sich damit als unbegründet.
Die Rüge, die fragliche Einschränkung der Glaubens- und Gewissensfreiheit entbehre der erforderlichen gesetzlichen Grundlage, erweist sich damit als unbegründet.
2.6 2.6.1 Die Beschwerdeführer stellen auch ein überwiegendes öffentliches Interesse an einem obligatorischen Schwimmunterricht in Frage. Sie machen geltend, der neue bundesgerichtliche Leitentscheid (<ref-ruling>) verneine lediglich ein generelles Recht auf Dispensation vom Schwimmunterricht aus religiösen Gründen; er entbinde die kantonalen Behörden aber nicht davon, die Verhältnismässigkeit der Dispensationsverweigerung unter den jeweiligen Verhältnissen näher zu prüfen.
2.6.2 Die Vorinstanz hat sich bei der Beurteilung des öffentlichen Interesses und der Verhältnismässigkeit des Grundrechtseingriffs auf die Erwägungen und Wertungen des erwähnten Entscheids des Bundesgerichts abgestützt. Sie verwies vor allem auf das stark zu gewichtende Interesse an der Integration aller Schüler, unabhängig von ihrer Herkunft, Kultur und Religion. Der Eingriff sei auch nicht unverhältnismässig, weil der gemischtgeschlechtliche Schwimmunterricht nur für Kinder vor der Geschlechtsreife stattfinde und er durch flankierende Massnahmen (getrennte Umkleide- und Duschräume, Verwendung von körperbedeckenden Schwimmanzügen) gemildert werde.
2.6.3 Die Argumente, welche die Beschwerdeführer gegen diese Beurteilung vorbringen, richten sich vor allem gegen die Rechtsprechungsänderung, die das Bundesgericht vor etwas mehr als drei Jahren vollzogen hat. Sie beziehen sich denn auch auf Überlegungen, die der früheren Praxis (<ref-ruling> ff.) zugrunde lagen. Für eine erneute Änderung der Rechtsprechung bedürfte es gewichtiger Gründe (vgl. <ref-ruling> E. 3 S. 82). Solche werden von den Beschwerdeführern nicht dargetan und sind auch nicht ersichtlich. Die Erwägungen zur Integration muslimischer Bevölkerungskreise gelten vielmehr nach wie vor (<ref-ruling> E. 7.2 S. 87 f.). Es besteht daher kein Anlass, die neue Rechtsprechung einer Überprüfung zu unterziehen.
2.6.4 Schliesslich legen die Beschwerdeführer auch keine besonderen Verhältnisse dar, die auch nach der neuen Praxis eine Dispensation ihrer Töchter vom Schwimmunterricht rechtfertigten. Dem Umstand, dass die Kinder, für die eine Dispensation verlangt wird, das Schwimmen ausserhalb der Schule erlernen, mass das Bundesgericht bereits im letzten Urteil kein wesentliches Gewicht bei. Denn es gehe nicht nur um den Inhalt des Lehrstoffs, sondern auch um die äusseren Bedingungen des Unterrichts. Die soziale Einbindungsfunktion der Schule erfordere, dass sie für alle obligatorisch sei und Dispensationen nur mit Zurückhaltung erteilt würden (<ref-ruling> E. 7.2 S. 89). Aus diesem Grund erscheint auch das weitere Argument der Beschwerdeführer nicht ausschlaggebend, Dispensationsgesuche von Muslimen für den Schwimmunterricht seien sehr selten und vermöchten den Unterrichtsbetrieb nicht zu stören. Die neue Praxis betont demgegenüber den grundsätzlichen Vorrang der schulischen Pflichten vor der Beachtung religiöser Gebote einzelner Bevölkerungsteile. Aus diesem Grund geht auch der Vergleich mit Dispensationen, die aus gesundheitlichen Gründen erteilt werden, fehl.
Die Beschwerde ist daher auch in dem Umfang unbegründet, in dem sie das erforderliche öffentliche Interesse und die Verhältnismässigkeit des Grundrechtseingriffs in Frage stellt.
3. Das Rechtsmittel der Beschwerdeführer ist demnach abzuweisen, soweit darauf einzutreten ist. Da es im Lichte der erwähnten bundesgerichtlichen Rechtsprechung zudem als aussichtslos erschien, ist ebenfalls das Gesuch um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren abzuweisen. Ausgangsgemäss sind die Kosten des bundesgerichtlichen Verfahrens den Beschwerdeführern zu gleichen Teilen und unter solidarischer Haftung aufzuerlegen (Art. 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern zu gleichen Teilen und unter solidarischer Haftung auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 7. März 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Küng