Faits: A. X._ est une association syndicale dont B._, député du parti socialiste au Grand Conseil, a assumé les fonctions de secrétaire général jusqu'à son élection au Conseil d'Etat le 2 mars 2003. A._ s'est affilié à X._ en 1992 et a été élu l'année suivante en tant que juge prud'homme sur la liste présentée par le syndicat. Son mandat a par la suite été renouvelé. Le 22 septembre 2000, X._, sous la signature de B._, a engagé A._, à titre temporaire et pour une durée indéterminée, en tant que juriste occupé à 20%, taux d'occupation qui a été porté à 40% au mois de décembre 2000. Par lettre du 28 décembre 2000, X._ a confirmé l'engagement de A._, à plein temps pour une durée indéterminée, en qualité de juriste et d'adjoint à la direction de la caisse de chômage du syndicat. A l'époque, A._ devait en particulier remplacer l'une des collaboratrices de la caisse de chômage, absente jusqu'en juin 2001. X._ avait aussi conçu, mais sans que le projet soit définitivement arrêté, qu'il se charge ensuite de la formation juridique de divers employés. A._, qui avait obtenu son brevet d'avocat en novembre 2000, envisageait de son côté de s'établir à son compte, sans pouvoir toutefois prédire l'ampleur que revêtirait cette future activité. Le 12 mars 2001, il a ouvert la Permanence juridique de Y._ Sàrl avec trois autres avocats et juristes. A la fin du mois suivant, à l'occasion d'une discussion dans un établissement public, B._ a appris que A._ avait délivré des avis de droit destinés au Centre G._ et qu'il était l'un des responsables pour la Suisse de l'Eglise Z._, aussi connue sous le nom de secte W._. Reprenant le curriculum vitae que son collaborateur avait remis lors de l'engagement, B._ a constaté qu'une grande partie des précédents employeurs mentionnés dans le document étaient liés à la secte W._. Il a été établi que A._ avait conservé, même après 1994, certains liens avec l'Eglise Z._, notamment qu'il avait participé à un stage organisé en Asie en 1997, était resté administrateur d'une société contrôlée par l'un des disciples du fondateur jusqu'en mars 2002 ou 2003 et avait reçu des procurations d'un proche de celui-ci, l'autorisant à exercer le droit de vote rattaché aux actions de la société deux ans auparavant. Estimant cette orientation incompatible avec des activités syndicales, X._ a décidé de se séparer de A._. Le 31 mai 2001, B._ a convoqué A._ et lui a signifié son licenciement pour la fin du mois suivant, motivé par son appartenance à la secte W._, ainsi que par ses sympathies avec des partis politiques de droite, tenues pour inconciliables avec les activités de X._. Il s'est aussi étonné de ne pas avoir été prévenu par son collaborateur que celui-ci exploitait la Permanence juridique de Y._ Sàrl. Dans une lettre remise en main propre à l'employé, il a encore justifié la résiliation par le fait que sa mission temporaire de juriste était arrivée à son terme et que des raisons budgétaires ne permettaient pas de la prolonger. B._ a enfin avisé A._ qu'il était libéré de son obligation de travailler durant le préavis de congé. Le matin du même jour, B._ a réuni l'ensemble du personnel de X._, en l'avisant du licenciement de A._ dû aux liens que celui-ci entretenait avec la secte W._. Dans une note diffusée quelques heures plus tard, les collaborateurs ont été invités à garder confidentielles les informations qui leur avaient été communiquées. Les employés se sont également vu adresser des recommandations d'éviter à l'avenir tout contact avec A._ et des membres du syndicat ont été avisés que les liens de confiance avec lui étaient rompus. A._ s'est trouvé en incapacité de travail du 12 au 15 juin 2001. Dans l'optique d'une prochaine audience, celui-ci a reçu à la Permanence juridique de Y._ Sàrl, le 15 juin 2001, trois personnes affiliée à X._, dont il avait défendu les intérêts dans le cadre de procédures prud'homales et qui avaient obtenu l'accord du syndicat pour que celui-ci continue de s'occuper de leur dossier. Par lettre du 18 juin 2001, B._, agissant au nom de X._, a licencié A._ avec effet immédiat, au motif qu'il avait travaillé alors qu'il se trouvait en incapacité de travail. Dans une entrevue accordée à un collaborateur du journal C._ au mois de décembre 2001, B._ s'est exprimé sur la procédure et sur ses origines. Il a reproché à A._ de lui avoir dissimulé son rôle dans la direction de la secte W._, ainsi que son attachement à des partis politiques de droite, tout en ayant cherché à infiltrer "par une stratégie d'entrisme" un syndicat dont il ne partageait pas les idées. A la suite de l'entretien, C._ a publié un article de trois pages reproduisant les propos de B._ sur l'affaire, accompagné des photographies des deux intéressés. L'article mettait encore en relief le fait que A._ s'était simultanément efforcé de faire prévaloir ses idées spirituelles et ses intérêts matériels au travers de l'empire économique de la secte W._ et que, politiquement, il avait encore milité au sein de partis d'extrême droite. B. Le 13 août 2001, A._ a actionné X._ en paiement de diverses sommes d'un montant total de plus de 115'000 fr. devant le Tribunal des prud'hommes du canton de Genève. Par jugement du 5 août 2002, celui-ci a notamment considéré que la première résiliation avait un caractère abusif au sens de l'art. 336 al. 1 let. b CO et que le second licenciement avec effet immédiat ne se fondait sur aucun juste motif. Pour ces raisons et considérant en outre que A._ avait été traité de manière choquante, les premiers juges lui ont en particulier alloué une indemnité globale de 19'000 fr. Statuant par arrêt du 9 février 2004 sur appel de X._ et appel incident de A._, la Cour d'appel de la juridiction des prud'hommes a condamné X._ à payer à A._ les sommes de 10'342 fr. 60 brut plus intérêt à 5% l'an dès le 19 juin 2001, 7'000 fr. net plus intérêt à 5% l'an dès le 19 juin 2001 et 15'000 fr. net plus intérêt à 5% l'an dès le 15 novembre 2001. C. X._ (la défenderesse) interjette un recours en réforme au Tribunal fédéral. Elle conclut à l'annulation de l'arrêt du 9 février 2004 en tant qu'il la condamne à payer à A._ la somme de 15'000 fr. net plus intérêt à 5% l'an dès le 15 novembre 2001 et au déboutement de celui-ci de ses conclusions en paiement d'une indemnité pour tort moral, avec suite de dépens. Parallèlement à ses conclusions tendant au rejet du recours principal, A._ (le demandeur) forme un recours joint dans lequel il requiert l'annulation de l'arrêt entrepris en tant qu'il le déboute de ses conclusions relatives au congé du 31 mai 2001, la constatation du caractère abusif de celui-ci ainsi que la condamnation de X._ à lui payer de ce fait la somme de 12'000 fr. et à lui rembourser la totalité de l'émolument d'appel cantonal, le tout avec suite de frais et dépens. X._ conclut au rejet du recours joint dans la mesure où il est recevable, avec suite de dépens.