Sachverhalt:
A. Mit Urteil des Strafgerichtspräsidenten Basel-Stadt vom 23. Dezember 2009 wurden X._ und Y._ der mehrfachen Nötigung (<ref-law>) schuldig gesprochen. Die beiden Verurteilten erklärten am 30. Dezember 2009 die Appellation gegen dieses Urteil.
Mit Schreiben vom 1. April 2011 an das zur Beurteilung der Appellation zuständige Appellationsgericht des Kantons Basel-Stadt stellten X._ und Y._ ein Ausstandsbegehren gegen die zuständige Staatsanwältin Franziska Frei und beantragten, die Appellationsantwort der Staatsanwältin vom 16. Februar 2011 sei aus den Akten zu entfernen, und es sei ein ausserordentlicher Staatsanwalt einzusetzen und mit der Ausarbeitung einer (neuen) Appellationsantwort zu beauftragen. Begründet wurde die Befangenheit der Staatsanwältin Franziska Frei mit dem Umstand, dass X._ nach dem erstinstanzlichen Verfahren Strafanzeigen gegen die Staatsanwältin wegen Amtsmissbrauchs, Drohung und Nötigung eingereicht hatte.
Mit Verfügung vom 12. April 2011 wies das Appellationsgericht das Ausstandsbegehren gegen die Staatsanwältin Franziska Frei mit der Begründung ab, die Rüge sei verspätet erhoben worden.
Mit Gesuch vom 14. April 2011 ersuchten X._ und Y._ das Appellationsgericht die Verfügung vom 12. April 2011 in Wiedererwägung zu ziehen. Das Appellationsgericht trat mit Verfügung vom 20. April 2011 auf das Wiedererwägungsgesuch nicht ein.
B. Mit Eingabe vom 29. April 2011 führen X._ und Y._ Beschwerde in Strafsachen an das Bundesgericht mit den Anträgen, die Verfügung vom 12. April 2011 sei aufzuheben, und das Appellationsgericht des Kantons Basel-Stadt sei anzuweisen, dem Ausstandsbegehren vom 1. April 2011 stattzugeben und für das laufende Verfahren einen ausserordentlichen Staatsanwalt einzusetzen; zudem sei der Beschwerde die aufschiebende Wirkung zu gewähren.
Das Appellationsgericht beantragt die Beschwerdeabweisung. Die Staatsanwältin Franziska Frei verzichtet auf eine Vernehmlassung. In ihrer abschliessenden Stellungnahme vom 21. Juni 2011 halten die Beschwerdeführer an ihrer Beschwerde fest.

Erwägungen:
1. 1.1 Die Beschwerde in Strafsachen gegen einen selbstständig eröffneten strafprozessualen Zwischenentscheid betreffend Ausstand von Mitgliedern der Strafverfolgungsorgane ist grundsätzlich zulässig (Art. 78 und 92 BGG).
1.2 Die Beschwerde gegen einen Entscheid ist innert 30 Tagen nach der Eröffnung des angefochtenen Entscheids beim Bundesgericht einzureichen (<ref-law>), wobei die Beschwerdeschrift die Begehren und deren Begründung zu enthalten hat (<ref-law>). Nach Ablauf der Beschwerdefrist können die Begehren nicht mehr ausgeweitet, sondern nur noch eingeschränkt werden. Soweit die Beschwerdeführer daher in ihrer Replik vom 21. Juni 2011 neue Anträge stellen, die über die Anträge ihrer Beschwerdeschrift hinausgehen, ist darauf nicht einzutreten (Urteil des Bundesgerichts 1C_464/2010 vom 26. Mai 2011 E. 1.3).
1.3 Nach Art. 81 Abs. 1 lit. a und b BGG ist zur Beschwerde berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat.
Das Interesse der Beschwerdeführer muss aktuell sein, das heisst auch im Zeitpunkt der Urteilsfällung noch bestehen. Das Bundesgericht verzichtet lediglich ausnahmsweise auf das Erfordernis des aktuellen praktischen Interesses, so wenn sich die aufgeworfenen Fragen unter gleichen oder ähnlichen Umständen jederzeit wieder stellen können, eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre und die Beantwortung wegen deren grundsätzlicher Bedeutung im öffentlichen Interesse liegt (<ref-ruling> E. 1.1 S. 81 mit Hinweis).
1.4 Das Appellationsgericht hat an seiner Verhandlung vom 3. Mai 2011 das Ausstandsbegehren der Beschwerdeführer betreffend die Staatsanwältin Franziska Frei - welche seit der Einreichung des Ausstandsbegehrens keinerlei Verfahrenshandlungen mehr vorgenommen und auch an der zweitinstanzlichen Verhandlung nicht teilgenommen hat - abgewiesen. Mit Urteil gleichen Datums bestätigte das Appellationsgericht die erstinstanzliche Verurteilung der Beschwerdeführer wegen mehrfacher Nötigung (<ref-law>).
Damit ist das kantonale Verfahren abgeschlossen und es fehlt an einem aktuellen Interesse der Beschwerdeführer an der Beurteilung ihres Ausstandsbegehrens gegen die Staatsanwältin Franziska Frei und an der Behandlung ihrer Anträge, die von der Staatsanwältin am 16. Februar 2011 eingereichte Appellationsantwort sei aus den Akten zu entfernen, und es sei ein ausserordentlicher Staatsanwalt einzusetzen und mit der Ausarbeitung einer (neuen) Appellationsantwort zu beauftragen. Es liegt auch kein Fall vor, indem ausnahmsweise vom Erfordernis des aktuellen Interesses abgesehen werden kann.
Davon gingen im Übrigen ursprünglich auch die Beschwerdeführer aus, welche in ihrer Beschwerdeschrift - anders als in ihrer abschliessenden Stellungnahme - ausführten, "die Beschwerde wird gegenstandslos, wenn die bereits angesetzte Verhandlung mit der Staatsanwältin stattfindet".
2. 2.1 Erklärt das Bundesgericht einen Rechtsstreit als erledigt, entscheidet es mit summarischer Begründung über die Prozesskosten aufgrund der Sachlage vor Eintritt des Erledigungsgrundes (<ref-law> in Verbindung mit <ref-law> [SR 273]). Bei der Beurteilung der Kosten- und Entschädigungsfolgen ist somit in erster Linie auf den mutmasslichen Ausgang des Prozesses abzustellen. Dem Bundesgericht steht dabei ein weites Ermessen zu. Nach ständiger Praxis kann es nicht darum gehen, bei der Beurteilung des Kostenpunkts über die materielle Begründetheit der Beschwerde abschliessend zu befinden (<ref-ruling> E. 2a S. 374 f.; <ref-ruling> E. 4a S. 494 f.; je mit Hinweisen).
Im Folgenden ist summarisch zu prüfen, ob die Beschwerde erfolgreich gewesen wäre.
2.2 Die Beschwerdeführer begründeten ihr gegen die Staatsanwältin Franziska Frei gerichtetes Ausstandsbegehren vom 1. April 2011 damit, dass zufolge der von der Beschwerdeführerin 1 gegen die Staatsanwältin am 17. und 21. Mai 2010 eingereichten Strafanzeigen wegen Amtsmissbrauchs, Drohung und Nötigung bei objektiver Betrachtung der Anschein der Befangenheit und die Gefahr der Voreingenommenheit bestehe.
Nach der bundesgerichtlichen Rechtsprechung wird gestützt auf den auch für Private geltenden Grundsatz von Treu und Glauben und das Verbot des Rechtsmissbrauchs (<ref-law>) verlangt, dass ein Ausstandsgrund sofort nach dessen Kenntnis geltend gemacht wird. Wer sich stillschweigend auf ein Verfahren einlässt, verwirkt den Anspruch auf spätere Anrufung der vermeintlich verletzten Ausstandsbestimmungen (<ref-ruling> E. 4.3 S. 496).
Die Beschwerdeführer hatten mit der Einreichung der Strafanzeigen im Mai 2010 Kenntnis der Fakten, auf welche sie ihren Befangenheitsantrag stützen. Dementsprechend wäre es ihnen möglich gewesen, ihr Ausstandsbegehren bereits zu diesem Zeitpunkt zu stellen. Stattdessen warteten sie hiermit bis zum 1. April 2011, das heisst bis nach dem Eingang der Appellationsantwort der angeblich befangenen Staatsanwältin vom 16. Februar 2011, zu. Eine summarische Prüfung ergibt daher, dass die Vorinstanz das Ausstandsbegehren zu Recht mit der Begründung abgewiesen hat, die Rüge sei verspätet erhoben worden. Demzufolge kann der Vorinstanz auch keine Verletzung ihrer Begründungspflicht als Ausfluss des Anspruchs der Beschwerdeführer auf rechtliches Gehör angelastet werden.
Im Übrigen wäre die Beschwerde aufgrund einer summarischen Prüfung auch materiell abzuweisen. Eine Partei kann nicht aus eigenem Verhalten einen Ausstandsgrund bei der in einer Strafbehörde tätigen Person ableiten. Die Einreichung einer Strafanzeige gegen die zuständige Staatsanwältin kann deshalb für sich allein keinen Anschein der Befangenheit begründen. Dies ergibt sich bereits daraus, dass andernfalls einer Partei hierdurch die Möglichkeit eröffnet würde, den Ausstandsgrund bewusst herbeizuführen und so Einfluss auf die Besetzung der Behörden zu nehmen (Urteil des Bundesgerichts 1P.514/2002 vom 13. Februar 2003 E. 2.5; Markus Boog, Basler Kommentar StPO 2011, N. 41 zu Art. 56). Folglich bestand für die Vorinstanz vorliegend entgegen den Ausführungen in der Beschwerde auch kein Grund für ein Vorgehen von Amtes wegen.
3. Diesem Ausgang des bundesgerichtlichen Verfahrens entsprechend tragen die Beschwerdeführer die Gerichtskosten (<ref-law>).

Demnach verfügt der Einzelrichter:
1. Die Beschwerde wird als gegenstandslos geworden vom Geschäftsverzeichnis abgeschrieben.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3. Diese Verfügung wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Statthalterin, schriftlich mitgeteilt.
Lausanne, 27. Juni 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Einzelrichter: Der Gerichtsschreiber:
Aemisegger Stohner