Sachverhalt: A. Die B._ AG mit Sitz in U._ (Arbeitgeberin, Klägerin und Beschwerdegegnerin) betreibt ein Personalvermittlungsunternehmen. A._ (Arbeitnehmer, Beklagter und Beschwerdeführer) war ab 20. Juni 2011 als Personalberater bei der B._ AG angestellt. Im Arbeitsvertrag vom 21./22. Juni 2011 vereinbarten die Parteien was folgt: "8. Der Mitarbeiter verpflichtet sich, nach Beendigung des Arbeitsverhältnisses bei der B._ AG, während zwei Jahren, in einem Umkreis von 100 km um seinem Hauptarbeitsplatz, die B._ AG in keiner Art und Weise zu konkurrenzieren. lnsbesondere verpflichtet er sich, weder auf eigene nach auf fremde Rechnung ein Geschäft zu betreiben, das mit B._ AG in Wettbewerb steht, oder dessen Zweck in der Anwerbung und zur Verfügungstellung oder Vermittlung von Personal besteht. 9. Für jede Nichteinhaltung der in Artikel 7 und 8 aufgeführten Verpflichtungen und insbesondere bei Übertretung des Konkurrenzverbotes schuldet der Mitarbeiter eine Konventionalstrafe in der Höhe des sechsfachen Monatsgehaltes (brutto inklusive Erfolgsbeteiligung), welches bei Beendigung des Arbeitsverhältnisses bestand. Die Zahlung der Konventionalstrafe befreit den Mitarbeiter nicht von der Einhaltung der oben erwähnten Bestimmungen und des Konkurrenzverbotes, und er bleibt im Weiteren für jeden der B._ AG zugefügten Schaden vollumfänglich ersatzpflichtig. Die B._ AG ist berechtigt, neben der Leistung der Konventionalstrafe und dem Ersatz des weiteren Schadens, die unmittelbare Beseitigung des vertragswidrigen Zustandes (Aktenrückgabe, Einhaltung des Konkurrenzverbotes usw.) zu verlangen." Mit Schreiben vom 28. Juni 2012 kündigte die Arbeitgeberin das Arbeitsverhältnis "unter Einhaltung der Kündigungsfrist von 2 Monaten auf den 31. August 2012". Im Schreiben wurde ausdrücklich festgehalten, dass das Konkurrenzverbot bestehen bleibe. Der Arbeitnehmer unterzeichnete dieses Schreiben neben einer Klausel mit dem Wortlaut: "Gelesen und akzeptiert. " In der Folge nahm der Arbeitnehmer eine neue Tätigkeit als Personalberater bei der C._ AG in U._ auf. B. B.a. Mit Klage vom 20. September 2013 beantragte die Arbeitgeberin dem Arbeitsgericht Baden, der Arbeitnehmer sei zur Zahlung einer Konventionalstrafe von Fr. 25'800.-- nebst Zins zu 5 % seit 5. Juni 2013 zu verurteilen. Der Arbeitnehmer beantragte in seiner Klageantwort die Abweisung der Klage und erhob seinerseits Widerklage auf Zahlung von Fr. 4'300.-- für "Lohn für die Verlängerung der krankheitsbedingten Kündigungsfrist " nebst Zins zu 5 % seit 30. September 2012. Mit Entscheid vom 12. Januar 2015 hiess das Arbeitsgericht die Klage vollumfänglich gut und wies die Widerklage ab, soweit es darauf eintrat. B.b. Dagegen erhob der Arbeitnehmer Berufung beim Obergericht des Kantons Aargau mit dem Antrag, das Urteil des Arbeitsgerichts sei aufzuheben, die Klage sei abzuweisen und die Widerklage sei gutzuheissen. Mit Entscheid vom 20. Oktober 2015 wies das Obergericht die Berufung ab. Wie bereits das Arbeitsgericht kam das Obergericht zum Schluss, dass das Konkurrenzverbot, das die Parteien in den Ziffern 8 und 9 des Arbeitsvertrags vereinbart hatten, gültig zustande gekommen und wirksam sei. Art. 340c Abs. 2 OR gelange vorliegend nicht zur Anwendung, da die Parteien das Arbeitsverhältnis nach ihrem subjektiv übereinstimmendem Willen durch einen Aufhebungsvertrag aufgelöst hätten. Die (einseitige) Kündigung durch die Arbeitgeberin vom 28. Juni 2012 sei lediglich simuliert gewesen. C. Mit Beschwerde in Zivilsachen beantragt der Arbeitnehmer dem Bundesgericht, es sei der Entscheid des Obergerichts aufzuheben, die Klage sei abzuweisen und die Widerklage sei gutzuheissen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Die Arbeitgeberin beantragt in ihrer Vernehmlassung die Abweisung der Beschwerde, soweit Eintreten. Die Vorinstanz hat auf Vernehmlassung verzichtet. Der Arbeitnehmer hat eine Replik eingereicht. D. Mit Präsidialverfügung vom 22. Januar 2016 wurde der Beschwerde die aufschiebende Wirkung erteilt.