Aus den Erwägungen:
4.1. Die fristlose Auflösung ist ein Notventil und als solches stets zurückhaltend zu handhaben. Voraussetzung dafür ist das Vorliegen eines wichtigen Grundes (Art. 337 Abs. 1 OR). Ein solcher liegt immer dann vor, wenn dem Kündigenden nach Treu und Glauben nicht zuzumuten ist, das Arbeitsverhältnis durch ordentliche Kündigung zu beenden (Art. 337 Abs. 2 OR). Das Vertrauensverhältnis zwischen den Parteien muss derart gestört sein, dass die sofortige und fristlose Auflösung des Arbeitsverhältnisses als einziger Ausweg erscheint (BGE 116 II 142 = JAR 1991 S. 141). Wann das der Fall ist, entscheidet im Streitfall der Richter nach seinem Ermessen (Art. 337 Abs. 3 OR). Die Beweislast für die Tatsachen, aus welchen die Berechtigung zur ausserordentlichen Kündigung abgeleitet wird, obliegt der Partei, welche die Kündigung erklärt hat (Rehbinder, Berner Komm., N 2 zu Art. 337 OR; Staehelin/Vischer, Zürcher Komm., N 42 zu Art. 337 OR, JAR 1989 S. 139 und JAR 1986 S. 151).
4.2. Vorliegend macht der Beklagte geltend, er habe im Oktober 1995 aufgrund der Aussage von R.K. von der K. AG, er werde sich um die notwendige Bewilligung bemühen, und der Zusicherung des Klägers, er sei im Besitz der Arbeitsbewilligung, darauf vertrauen dürfen, dass der Kläger nun zum Stellenantritt tatsächlich berechtigt sei.
Es ist grundsätzlich Sache des Arbeitgebers, der einen ausländischen Arbeitnehmer anstellt, alle öffentlich-rechtlichen Schritte zu unternehmen, um das Arbeitsverhältnis zu sichern (Rehbinder, Berner Komm., N 8 zu Art. 324 OR; Staehelin/Vischer, Zürcher Komm., N 11 zu Art. 324 OR; JAR 1981 S. 135 f.). Der Arbeitgeber darf keinen Ausländer eine Stelle antreten lassen, ohne sich vorher durch Einsicht in den Ausländerausweis oder Nachfrage bei der Fremdenpolizei zu vergewissern, dass der Arbeitnehmer zum Antritt dieser Stelle berechtigt ist (Art. 10 Abs. 1 Verordnung über die Begrenzung der Zahl der Ausländer [BVO], SR 823.21). Demzufolge hätte sich der Beklagte im Zeitpunkt der Neueinstellung des Klägers nicht einfach auf die Richtigkeit der angeblich von diesem abgegebenen Zusicherung verlassen dürfen. Der Beklagte musste sich der vorerwähnten Pflichten umso mehr bewusst sein, als er bereits einmal gebüsst worden war, weil er für den Kläger keine Bewilligung eingeholt hatte. Im weitern verkennt der Beklagte, dass eine allfällige von der K. AG für den Kläger eingeholte Arbeitsbewilligung ihn nicht von der Pflicht entbunden hätte, bei der Neueinstellung des Klägers erneut um eine Bewilligung nachzusuchen (vgl. Art. 29 Abs. 1 BVO, wonach bei Stellenwechsel die Einholung einer Bewilligung erforderlich ist). Wenn der Beklagte vorliegend erst rund sechs Wochen nach der Neueinstellung des Klägers festgestellt haben will, dass dieser nicht über die erforderliche Arbeitsbewilligung verfügte, hat er dies der eigenen Nachlässigkeit zuzuschreiben. Deshalb verhielt er sich wider Treu und Glauben, wenn er den Kläger im November 1995 unter Berufung auf die mangelnde fremdenpolizeiliche Bewilligung fristlos entliess. Es wäre nach der Entdeckung des Mangels die Pflicht des Beklagten gewesen, dem Grund für die angebliche Falschinformation nachzugehen und sich umgehend um die Einholung der erforderlichen Bewilligung zu bemühen; die Frage einer fristlosen Kündigung hätte sich allenfalls nach einer Verweigerung der Bewilligung gestellt (Rapp, in: Basler Festgabe zum Schweizerischen Juristentag 1985, Fremdenpolizeiliche Arbeitsbewilligung und Arbeitsvertrag, S. 293; BGE 114 II 279ff. = Pra 78 [1989] Nr. 37 S. 151). Zusammenfassend erweist sich die vom Beklagten ausgesprochene fristlose Kündigung als ungerechtfertigt.