Sachverhalt: A. A.a. A._ (Kläger, Beschwerdeführer) absolvierte bei B._ (Beklagter, Beschwerdegegner) in den Jahren 2000 bis 2002 eine Anlehre als Fahrzeugwart und arbeitete in der Folge bei ihm in dieser Funktion. Dieses Arbeitsverhältnis wurde vom Beklagten auf Ende März 2006 ordentlich gekündigt. Ab 1. März 2007 war der Kläger wieder beim Beklagten angestellt. Am 1. Mai 2012 verwarnte der Beklagte den Kläger wie folgt: - Ihr Verhalten gegenüber unserer Kundschaft lässt zu wünschen übrig - Unkollegiales Verhalten gegenüber Arbeitskollege und Vorgesetzten - Unpünktliches Erscheinen am Arbeitsplatz - Nicht tolerierbare Arbeitsverweigerung (wie z.B. das Reineigen [recte wohl Reinigen] des Garagenbetriebs, der Werkzeuge, Unterstützung ihrer Arbeitskollegen etc.) - Ihre Einstellung zur Arbeit ist nicht nur ungenügend, sondern gibt auch immer wieder Grund zur Diskussion im Team". Die Verwarnung hält abschliessend fest, falls die festgehaltenen Punkte nochmals Anlass zur Reklamation geben sollten, sähe sich der Beklagte gezwungen, dem Kläger fristlos zu kündigen. A.b. Am 21. Januar 2014 kündigte der Beklagte dem Kläger (mündlich) fristlos. In der Arbeitgeberbescheinigung zu Handen des RAV gab er als Kündigungsgrund an: "Nicht Teamfähig - Arbeitsverweigerung - fern bleiben des Arbeitsplatz - Reifendiebstahl - unfreundlich zu Kunden usw. Verwarnung/Abmahnung vom 3.5.12". In der von der Rechtsschutzversicherung des Beschwerdeführers mit Schreiben vom 4. Februar 2014 verlangten (Kurz-) Begründung nannte er: "Neu: Reifendiebstahl, Arbeitgeber nicht anwesend: verlassen des Arbeitsplatz. Hier handelt es sich nicht um 10min. um Std. und das regelmässig. usw. Alle Unterlagen haben wir dem RAV zugestellt". B. Mit Klage vom 13. Oktober 2014 beim Bezirksgericht Laufenburg beantragte der Kläger, der Beklagte sei zur Bezahlung von Fr. 23'785.40 nebst Zins zu 5 % seit 21. Januar 2014 sowie einer (im einzelnen vorgegebenen) Berichtigung des Arbeitszeugnisses vom 14. April 2014 zu verpflichten; unter Kosten- und Entschädigungsfolge. Beim eingeklagten Betrag handelt es sich um entgangenen Lohn während der ordentlichen Kündigungsfrist und eine Pönale wegen ungerechtfertigter fristloser Entlassung. Das Bezirksgericht schützte die Klage mit Entscheid vom 15. Oktober 2015 teilweise (soweit das Arbeitszeugnis betreffend); im Übrigen wies es die Klage ab. Das Obergericht des Kantons Aargau wies die vom Kläger erhobene Berufung mit Entscheid vom 8. März 2016 ab. C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, das Urteil des Obergerichts sei aufzuheben und der Beschwerdegegner sei kostenfällig zu verpflichten, ihm Fr. 23'616.25 nebst Zins zu 5 % seit 21. Januar 2014 zu bezahlen. Der Beschwerdegegner trägt auf kostenfällige Abweisung der Beschwerde an, soweit darauf eingetreten werden könne. Das Obergericht hat auf eine Vernehmlassung verzichtet.