Sachverhalt: Sachverhalt: A. A._ (Kläger) war seit dem 1. Januar 1993 als Filialleiter der B._ AG (Beklagte) im C._-Shopping angestellt, wo Videos, DVDs und Computerspiele zum Kauf angeboten wurden. Er wurde an seinen freien Tagen durch D._ vertreten, die in der Filiale als Aushilfsverkäuferin tätig war. Anfangs Dezember 2001 meldete D._ der Verkaufsleitung der Beklagten verschiedene von ihr festgestellte Ungereimtheiten. Diese erweckten den Verdacht, der Kläger habe Artikel aus dem Sortiment gestohlen bzw. veruntreut. Die Beklagte erstattete deshalb am 10. Dezember 2001 Strafanzeige gegen den Kläger. Nachdem die Staatsanwaltschaft Basel-Stadt die Vorgesetzten des Klägers und D._ einvernommen hatte, liess sie den Kläger am 22. Januar 2002 polizeilich zur Einvernahme vorführen und durchsuchte gleichzeitig seine Wohnung. Dort wurde allerdings nichts beschlagnahmt. Am 23. Januar 2002 kündigte die Beklagte das Arbeitsverhältnis mit dem Kläger per 30. April 2002. Da der Kläger indessen seit diesem Tag krank geschrieben war, erwies sich diese Kündigung als nichtig. Nach Ablauf der gesetzlichen Sperrfrist von 180 Tagen kündigte die Beklagte dem Kläger mit Schreiben vom 25. Juli 2002 erneut auf den 31. Oktober 2002. Das Strafverfahren gegen den Kläger wurde nach weiteren Ermittlungen mit Beschluss der Staatsanwaltschaft vom 27. August 2002 eingestellt, da kein hinreichender Beweis des Tatbestandes bzw. keine rechtsgültigen Strafanträge für allfällige geringfügige Vermögensdelikte vorlagen. Das Strafverfahren gegen den Kläger wurde nach weiteren Ermittlungen mit Beschluss der Staatsanwaltschaft vom 27. August 2002 eingestellt, da kein hinreichender Beweis des Tatbestandes bzw. keine rechtsgültigen Strafanträge für allfällige geringfügige Vermögensdelikte vorlagen. B. Am 11. Februar 2003 klagte A._ beim Gewerblichen Schiedsgericht Basel-Stadt gegen die Beklagte auf Zahlung von sechs Bruttomonatslöhnen, d.h. Fr. 27'618.--, zuzüglich Zins als Entschädigung für missbräuchliche Kündigung. Mit Urteil vom 18. August 2003 wies das Gewerbliche Schiedsgericht die Klage ab. Eine gegen dieses Urteil gerichtete Beschwerde des Klägers wies der Ausschuss des Appellationsgerichts des Kantons Basel-Stadt am 13. Januar 2004 ab. B. Am 11. Februar 2003 klagte A._ beim Gewerblichen Schiedsgericht Basel-Stadt gegen die Beklagte auf Zahlung von sechs Bruttomonatslöhnen, d.h. Fr. 27'618.--, zuzüglich Zins als Entschädigung für missbräuchliche Kündigung. Mit Urteil vom 18. August 2003 wies das Gewerbliche Schiedsgericht die Klage ab. Eine gegen dieses Urteil gerichtete Beschwerde des Klägers wies der Ausschuss des Appellationsgerichts des Kantons Basel-Stadt am 13. Januar 2004 ab. C. Der Kläger führt gegen das Urteil des Appellationsgerichts eidgenössische Berufung. Er beantragt die Aufhebung des angefochtenen Urteils und die Gutheissung der Klage. Die Beklagte schliesst auf Abweisung des Rechtsmittels.