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. 