Sachverhalt:
A. Y._ vermietete am 3. Juni 2008 eine Drei-Zimmerwohnung in Basel an X._. Der Vertrag mit einem monatlichen Mietzins von Fr. 1'385.-- war mit einer Kündigungsfrist von drei Monaten auf Ende jeden Monats kündbar. Die Vermieterin kündigte den Mietvertrag mit eingeschriebenen Brief vom 12. Juli 2010 und unter Verwendung des offiziellen Formulars auf den 31. Oktober 2010.
B. B.a Der Mieter focht die Kündigung mit Schreiben vom 7. September 2010 bei der Schlichtungsstelle für Mietstreitigkeiten Basel-Stadt als missbräuchlich an und ersuchte gleichzeitig um Erstreckung des Mietverhältnisses. Die Schlichtungsverhandlungen scheiterten infolge Verpassens der Anfechtungsfrist.
Am 27. Oktober 2010 reichte der Mieter beim Zivilgericht des Kantons Basel-Stadt Klage ein, in der er hauptsächlich auf Aufhebung der Kündigung und subsidiär auf eine erstmalige Erstreckung des Mietverhältnissen um sechs Monate schloss. Die Vermieterin ihrerseits beantragte die Abweisung der Klage und den Erlass eines Räumungsbefehls.
Die Zivilgerichtspräsidentin entschied am 10. Januar 2011. Sie erachtete die Anfechtung als verspätet und lehnte eine Wiederherstellung der Anfechtungsfrist ab; sie trat demzufolge auf das Begehren des Mieters betreffend Anfechtung der Kündigung nicht ein und wies ihn an, die gemieteten Räumlichkeiten bis spätestens am 15. März 2011 um 12.00 Uhr zu verlassen.
B.b Gegen das Urteil des Zivilgerichts reichte der Mieter Berufung beim Appellationsgericht des Kantons Basel-Stadt ein. Er schloss im Wesentlichen dahin, es sei die Unwirksamkeit der Kündigung festzustellen, eventualiter sei die Einsprachefrist wieder herzustellen und die Kündigung aufzuheben, eventualiter und pro forma sei das Mietverhältnis im maximal gesetzlich zulässigen Umfang zu erstrecken. Die Vermieterin schloss auf Abweisung der Berufung.
Mit Urteil vom 20. April 2011 wies das Appellationsgericht (Ausschuss) die Berufung ab und setzte dem Mieter Frist bis spätestens am 15. Juni 2011 um 12.00 Uhr, um die gemieteten Räumlichkeiten zu verlassen.
C. Gegen das Urteil des Appellationsgerichts legte der Mieter (nachfolgend: Beschwerdeführer) Beschwerde in Zivilsachen beim Bundesgericht ein. Er schliesst hauptsächlich dahin, es sei die Unwirksamkeit der Kündigung vom 12. Juli 2010 festzustellen, es sei der Räumungsbefehl aufzuheben und es sei ihm der Kündigungsschutz im gesetzlich maximal zulässigen Umfang zu bestätigen. Weiter sei der Beschwerde superprovisorisch die aufschiebende Wirkung zu erteilen.
Die Vermieterin (nachfolgend: Beschwerdegegnerin) schliesst in ihrer Vernehmlassung auf Abweisung der Beschwerde. Ihrer Beschwerdeantwort legte sie eine CD mit Tonaufnahmen angeblicher Beschimpfungen des Beschwerdeführers bei. Der Beschwerdeführer reichte daraufhin unaufgefordert eine Replik ein, in welcher er verlangt, dass die CD nicht berücksichtigt werde. Die Beschwerdegegnerin erklärte in der Folge, auf eine Stellungnahme zu verzichten.

Erwägungen:
1. Mit dem vorliegenden Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.
2. Im Beschwerdeverfahren vor Bundesgericht können keine neuen Tatsachen oder Beweismittel vorgebracht werden, es sei denn, erst der Entscheid der Vorinstanz gebe dazu Anlass (Art. 99 Abs. 1 BGG). Das trifft für die mit der Beschwerdeantwort eingereichte CD nicht zu. Sie bleibt folglich unbeachtlich; von ihrem Inhalt wird keine Kenntnis genommen.
3. Will eine Partei die Kündigung eines Mietvertrages anfechten, so muss sie das Begehren innert dreissig Tagen nach Empfang der Kündigung bei der Schlichtungsstelle einreichen (Art. 273 Abs. 1 OR); das ist im vorliegenden Fall unbestrittenermassen nicht geschehen. Sodann schliesst der Beschwerdeführer nicht mehr auf Wiederherstellung der Anfechtungsfrist. Auf diese Punkte ist nicht weiter einzugehen.
4. Der Beschwerdeführer macht geltend, die Kündigung sei unwirksam bzw. nichtig, weil sie im Formular mit dem lapidaren Hinweis auf "§ 271.c" unklar begründet wurde.
4.1 Die strittige Kündigung erfolgte gemäss den vertraglich vereinbarten Fristen und Terminen und stellt folglich eine ordentliche Kündigung dar. Der allfällige Verweis des Vermieters auf einen Kündigungsgrund, der eine ausserordentliche Kündigung rechtfertigen würde, macht die ordentliche Kündigung nicht zu einer ausserordentlichen.
Eine ordentliche Kündigung muss nicht begründet werden, um gültig zu sein; es genügt, wie vorliegend geschehen, der Hinweis auf dem Kündigungsformular, dass der Vermieter die Kündigung auf Verlangen des Mieters begründen muss (Art. 271 Abs. 2 OR; Art. 9 Abs. 1 lit. c der Verordnung vom 9. Mai 1990 über die Miete und Pacht von Wohn- und Geschäftsräumen [VMWG; SR 221.213.11]). Die Begründung ist an keine Form gebunden; sie kann auch erst mündlich vor der Schlichtungsstelle vorgebracht werden (Urteil 4C.400/2001 vom 4. März 2002 E. 2, publ. in: Pra 2002 Nr. 110).
Die "lapidare" Begründung im Kündigungsschreiben steht im Übrigen nicht im Widerspruch zu den Gründen, welche die Beschwerdegegnerin nachträglich für die Kündigung angegeben hat. Die Begründung auf dem Formular ist grundsätzlich nichtssagend, denn im OR gibt es weder "§§" noch einen Art. 271c oder einen Art. 271 lit. c. Mit "§ 271.c" könnte allenfalls Art. 271a Abs. 3 lit. c OR gemeint gewesen sein, laut welchem eine Kündigung nicht anfechtbar ist, wenn sie wegen schwerer Verletzung der Pflicht des Mieters zu Sorgfalt und Rücksichtnahme erfolgt; auf solche Pflichtverletzungen hat sich die Beschwerdegegnerin in der Folge aber gerade berufen.
Der Beschwerdeführer verweist auf ein Schreiben des Verwalters der Nachbarliegenschaft, das ihm gleichzeitig mit dem Kündigungsformular zugegangen sei. Davon steht im angefochtenen Entscheid des Appellationsgerichts aber nichts, und der Beschwerdeführer beschränkt sich auf Behauptungen, so dass eine ausnahmsweise Ergänzung des Sachverhalts zum vornherein ausser Betracht fällt (vgl. <ref-ruling> E. 1.4.3, 133 III 462 E. 2.4, 133 III 393 E. 7.1). Da das Bundesgericht an den von der Vorinstanz festgestellten Sachverhalt gebunden ist (Art. 105 Abs. 2 BGG), ist folglich nicht weiter darauf einzugehen.
4.2 Unter diesen Umständen kann keine Rede davon sein, dass die Kündigung mangels klarer Begründung im Kündigungsschreiben nichtig wäre. Die weitschweifigen Ausführungen des Beschwerdeführers zu dieser Frage sind unbeachtlich.
5. Der Beschwerdeführer rügt sodann eine Verletzung des rechtlichen Gehörs und des Rechts auf Beweis. Es geht dabei um den Beweis dafür, dass die vorgebrachten Kündigungsgründe nicht bestehen.
Der Beschwerdeführer hat die Anfechtungsfrist verpasst. Die Kündigung ist folglich unanfechtbar, ungeachtet davon, ob die von der Beschwerdegegnerin erwähnten Gründe für die Kündigung bestehen oder nicht. Darüber war folglich auch nicht Beweis zu erheben.
6. Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit überhaupt darauf einzutreten ist.
Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
2. Die Kosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat der Beschwerdegegnerin Fr. 3'000.-- als Parteientschädigung zu bezahlen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 3. August 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Hurni