Faits:
A. Par contrat signé le 26 janvier 2007, A._ International SA (ci-après: l'employeuse), société active dans le commerce de vins, a engagé X._ (ci-après: l'employé) en qualité de directeur des exportations, pour une durée indéterminée à partir du 12 février 2007.
Les conditions de travail proposées à l'employé comprenaient un temps d'essai de six mois à Londres. Par la suite, si la période d'essai se révélait satisfaisante pour les deux parties, l'employé devait être transféré vers la Suisse ou Madrid.
Le contrat précisait que les frais de déménagement de l'employé de Londres en Suisse ou à Madrid seraient assumés par son employeuse. La performance de l'employé serait évaluée annuellement. Le délai de congé était fixé à trois mois.
X._ a commencé à travailler au service de la société le 12 février 2007, à Londres, où il résida pendant sept mois, laissant sa famille en Israël. L'employé et sa famille sont arrivés en Suisse à la fin du mois d'août 2007. L'employeuse a conclu un contrat de bail pour une maison, pour une année (soit jusqu'au 31 août 2008), et a pris le loyer à sa charge, ainsi que tous les frais de déménagement de la famille de l'employé, de même que les billets d'avion. Les enfants de X._ ont commencé l'année scolaire 2007-2008 à l'Ecole internationale de Berne. Les frais d'écolage étaient assumés par la société.
A la mi-octobre 2007, B._, président du conseil d'administration du groupe C._, dont A._ International SA fait partie, a annoncé un changement de stratégie commerciale au sein de l'entreprise. Le 23 novembre 2007, il s'est déplacé à Fribourg pour rencontrer X._.
Le 7 décembre 2007, B._, accompagné de D._, responsable des ressources humaines, est revenu à Fribourg pour remettre à l'employé la résiliation de son contrat de travail, avec libération de son obligation de travailler dès le 31 décembre 2007. Le motif de licenciement était le changement de stratégie de la société, lequel amenait la société à licencier plusieurs collaborateurs et à se passer du bureau de vente sis à Fribourg.
L'employé a contesté son congé par lettre du 18 mars 2008. Il a perçu son salaire jusqu'à la fin du mois de mars 2008. La famille X._ a pu rester dans la maison louée par la société jusqu'au 31 août 2008. L'épouse de l'employé et leurs deux enfants sont alors retournés en Israël.
B. Le 26 septembre 2008, l'employé a introduit une action en paiement auprès du Tribunal civil de l'arrondissement de la Sarine à l'encontre de son employeuse pour licenciement abusif. Ses conclusions portent sur un montant de 134'376 fr.05.
Par jugement du 10 août 2010, le Tribunal civil a admis la demande à concurrence de 73'333 fr.25 avec intérêts.
Par arrêt du 2 février 2011, la Ie cour d'appel civil du Tribunal cantonal fribourgeois a admis l'appel interjeté par l'employeuse et rejeté l'action de l'employé. En substance, elle a retenu que si la première n'a pas eu une attitude des plus correctes à l'égard du second en lui donnant son congé quelques mois après l'avoir transféré en Suisse, cela ne rendait pas pour autant le congé abusif.
C. L'employé exerce un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal du 2 février 2011. Il conclut, sous suite de frais et dépens, à son annulation et à ce que le jugement rendu le 10 août 2010 par le Tribunal civil de la Sarine, qui astreint l'employeuse à lui verser le montant de 73'333 fr.25, soit confirmé. Le recourant fait grief à l'autorité cantonale d'avoir transgressé les art. 336 et 328 al. 1 CO et il tire moyen de l'interdiction de l'abus de droit.
L'intimée conclut au rejet du recours et à la confirmation de l'arrêt cantonal.

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé dans son action en paiement (<ref-law>) et dirigé contre arrêt final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire pécuniaire en matière de droit du travail dont la valeur litigieuse atteint le seuil de 15'000 fr. (<ref-law>), le recours est en principe recevable puisqu'il a été déposé dans le délai (art. 48 al. 1 et 100 LTF) et la forme (<ref-law>) prévus par la loi.
1.2 Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.4 p. 400). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 1.4 p. 400).
Par exception à la règle selon laquelle il applique le droit d'office, il ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (<ref-law>).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401; <ref-ruling> consid. 8.1. p. 153) - ou en violation du droit au sens de l'<ref-law> (<ref-law>). Il incombe à la partie recourante, qui entend s'écarter des constatations de l'autorité précédente, d'expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (<ref-ruling> consid. 1.4 p. 287 s. et consid. 6.2 p. 288). Une rectification de l'état de fait ne peut être demandée que si elle est de nature à influer sur le sort de la cause (<ref-law>). Aucun fait nouveau, ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2. 2.1 A titre préalable, il faut observer que l'état de fait est dressé par la cour cantonale de telle manière qu'il n'est pas aisé de reconnaître clairement les faits que les juges considèrent comme établis et ceux qu'ils écartent (sur l'exigence, cf. arrêt 4A_231/2010 du 10 août 2010 consid. 2.2, in SJ 2010 I p. 497). Dans la partie "en fait" du jugement, la cour cantonale se limite à faire état de quelques points de fait incontestés (date de l'engagement de l'employé, des rencontres avec le président du conseil administration, de son licenciement, etc.). Dans la partie "en droit", l'appréciation des preuves et les faits retenus - que l'on distingue parfois difficilement du raisonnement juridique - sont mélangés avec des résumés de la décision de première instance (toutefois sans que la cour cantonale y renvoie), ainsi que des prises de position de la société intimée (devant la première instance et en appel), ce qui ne facilite pas la lecture de l'état de fait. Il est douteux que l'arrêt cantonal respecte ainsi les exigences posées à l'<ref-law>.
L'état de fait n'est toutefois pas complètement absent (pour ce cas de figure ayant conduit au renvoi à l'autorité cantonale: arrêt 4A_252/2007 du 15 novembre 2007 consid. 3.2). A bien lire l'arrêt entrepris, on peut quand même discerner les faits retenus décisifs. Le recourant semble d'ailleurs le reconnaître lui-même puisqu'il n'invoque pas la violation de l'<ref-law>.
Ainsi, la cour précédente a notamment retenu que l'employé n'a pas présenté d'indices suffisants permettant de douter de la réalité du motif du congé, soit le changement de stratégie commerciale de la société intimée. Elle souligne en particulier, en appréciant les preuves, que le recourant admet lui-même avoir assisté à la réunion des cadres de l'intimée, à la mi-octobre 2007, au cours de laquelle le président du conseil d'administration a présenté la nouvelle stratégie de la société (arrêt entrepris p. 5). Il a également été constaté que celui-ci a pris la peine de rencontrer deux fois l'employé après que la société a décidé de changer sa stratégie (arrêt entrepris p. 2). La juridiction précédente retient que la famille X._ a pu rester dans la maison louée par la société intimée jusqu'au 31 août 2008 (arrêt entrepris p. 2) et elle souligne que si le directeur général de l'intimée a dit au recourant, au cours des négociations précontractuelles, que la société voulait engager du personnel stable, ni une durée contractuelle minimale ni un plus long délai de résiliation n'ont été fixés (arrêt entrepris p. 7).
Ces constatations, qui figurent dans l'arrêt cantonal, sont suffisantes pour que la Cour de céans puisse contrôler de quelle manière le droit fédéral a été appliqué (cf. infra consid. 2.2.-2.4).
2.2 Le recourant soutient qu'un examen sérieux du cas fait apparaître que le motif économique, allégué par l'employeuse pour expliquer le congé, n'était qu'un prétexte et que la cour cantonale a transgressé l'<ref-law> en ne retenant pas le congé abusif. Il tente de démontrer, en renvoyant aux déclarations faites en audience, ainsi qu'à diverses pièces du dossier, que le véritable motif du licenciement était de se séparer de lui au plus vite pour la seule raison qu'il était "trop bien payé".
Le motif réel d'une résiliation relève du fait (<ref-ruling> consid. 2.3 p. 515; <ref-ruling> consid. 4.3 p. 540; <ref-ruling> consid. 4.1 p. 702). En alléguant un autre motif que celui retenu par la cour cantonale, le recourant présente son propre état de fait, qu'il oppose à celui retenu par la cour cantonale. Une telle manière de procéder ne correspond pas à la règle posée par l'<ref-law> (cf. supra consid. 1.3). Le recourant ne peut pas présenter différents éléments de faits extraits du dossier pour tenter de démontrer le motif de congé qu'il allègue. Cela impliquerait que le Tribunal fédéral substitue sa propre appréciation des preuves à celle de l'autorité cantonale et dresse lui-même un état de fait. Si une rectification de celui-ci est demandée en application de l'<ref-law>, le recourant doit indiquer, dans les motifs de son recours, quel est le fait qui aurait été constaté ou omis arbitrairement (art. 9 Cst.), en montrant par une argumentation précise, en se référant si possible aux pièces du dossier, que la position adoptée par la juridiction précédente est insoutenable; il faut encore qu'il apparaisse clairement que la rectification demandée est susceptible d'influer sur le sort de la cause (<ref-law>). Il ne sera donc pas entré en matière sur l'argumentation du recourant dans la mesure où celui-ci prétend que le licenciement serait abusif en se fondant sur un autre motif de congé que celui retenu dans l'arrêt attaqué.
Si l'on s'en tient aux constatations cantonales, il apparaît que les juges sont d'avis qu'on ne peut douter du motif du congé, soit de la réalité du changement de stratégie commerciale de la société intimée. La juridiction précédente appuie ce constat en observant que le recourant a lui-même admis avoir assisté à la réunion des cadres de l'intimée à Londres, à la mi-octobre 2007, au cours de laquelle le président du conseil d'administration a présenté cette nouvelle stratégie qui avait un effet direct sur la place de travail du recourant. Il ressort du procès-verbal de cette séance, reproduit en partie dans l'arrêt cantonal, que la poursuite de la nouvelle stratégie a conduit à supprimer environ quarante postes dans tout le groupe; dans l'équipe commerciale pour l'Europe centrale, quatre personnes ont été licenciées (deux en Suisse, dont le recourant, et deux en Allemagne). L'ancien directeur général de la société, qui a quitté l'intimée en février 2008, a d'ailleurs confirmé la réalité des congés, ayant lui-même donné des instructions en vue du licenciement d'un des deux collaborateurs de la société en Allemagne.
Ainsi, après avoir apprécié les preuves, la cour cantonale a établi le motif du congé. Au stade de la subsomption, on ne voit pas que la juridiction précédente ait violé l'<ref-law> en concluant que ce motif, qui ne constituait pas un simple prétexte, n'était pas à même d'établir le caractère abusif du licenciement.
Au demeurant, même à considérer que la cour cantonale n'aurait pas recherché le motif réel du licenciement (et qu'elle se serait seulement contentée du motif invoqué par l'intimée), le grief serait mal fondé. Le fardeau de la preuve du caractère abusif de la résiliation incombe à la partie qui s'est vue signifier le congé. Conscient du fait que la preuve est difficile à apporter, le Tribunal fédéral a précisé que le juge peut présumer en fait l'existence d'un congé abusif lorsque l'employé parvient à présenter des indices suffisants pour faire apparaître comme non réel le motif avancé par l'employeur. Si cette présomption facilite la preuve, elle n'a cependant pas pour effet d'en renverser le fardeau. Elle constitue, en définitive, une sorte de "preuve par indices". Le point de savoir si une telle présomption est établie ou non relève de l'appréciation des preuves - qui lie le Tribunal fédéral - et non de l'application du droit fédéral (arrêt 4C.121/2001 du 16 octobre 2001 consid. 3; arrêt 4C.27/1992 du 30 juin 1992 consid. 3a, in SJ 1993 p. 360). En l'espèce, la cour cantonale indique que le recourant n'a pas présenté d'indices suffisants permettant de douter de la réalité du changement de stratégie commerciale; le recourant, qui supporte dès lors l'échec de la preuve, ne tente pas de démontrer que l'autorité précédente aurait sombré dans l'arbitraire en tirant cette conclusion ou qu'elle aurait transgressé l'<ref-law> en refusant d'administrer des preuves régulièrement offertes portant sur des faits pertinents en droit (cf. <ref-ruling> consid. 5.4 p. 601 s.).
Dans la mesure de sa recevabilité, le grief doit être déclaré mal fondé.
2.3 Le recourant tire ensuite moyen de la transgression de l'<ref-law> en relation avec l'<ref-law>.
D'emblée, on observe que le recourant ne pose aucune question juridique. En réalité, il essaie seulement de substituer un autre état de fait à celui retenu par la cour cantonale, en vue de parvenir à une solution inverse sur la base des mêmes principes juridiques. Il tente notamment de démontrer que la résiliation du contrat de travail l'a plongé, lui et sa famille, dans une situation de détresse psychologique, que l'intimée a tenté de rompre son bail à loyer de manière anticipée et qu'elle a cessé de payer l'écolage de ses deux enfants. Faisant référence à divers allégués, ainsi qu'à certaines pièces du dossier, le recourant se limite à présenter sa version des faits, sans invoquer l'arbitraire (art. 9 Cst.) et sans fournir de motivation circonstanciée dans cette perspective. Une telle manière de procéder ne correspond pas aux règles posées par les art. 105 et 106 LTF et il n'y a pas lieu de tenir compte de l'état de fait présenté par le recourant.
Selon les constatations cantonales, le congé a été donné à l'employé, ainsi qu'à d'autres collaborateurs, en raison du changement de la stratégie commerciale de la société intimée. Après la réunion des cadres de mi-octobre 2007 (cf. supra consid. 2.2), le président du conseil d'administration s'est déplacé personnellement à Fribourg le 23 novembre 2007 pour y rencontrer le recourant. Vu la chronologie des événements, on peut raisonnablement penser que la discussion a porté sur le changement de stratégie - qui impliquait la suppression du bureau de Fribourg - et ses conséquences pour l'employé. Le 7 décembre 2007, le président du conseil d'administration, accompagné du responsable des ressources humaines, est revenu à Fribourg pour remettre à l'employé la résiliation de son contrat de travail. Il ressort également de l'arrêt cantonal que la famille X._ a pu rester dans la maison louée par la société jusqu'au 31 août 2008. Enfin, si, lors des négociations contractuelles, le directeur général de l'intimée a dit au recourant que celle-ci voulait engager du personnel stable, ni une durée contractuelle minimale ni un plus long délai de résiliation n'ont été fixés.
Cela étant, on ne discerne, sur la base de ces constatations, aucune atteinte grave aux droits de la personnalité pouvant faire apparaître la résiliation comme abusive (cf. <ref-ruling> consid. 2.3 p. 515 et les arrêts cités). Le simple fait que le directeur général ait laissé entendre au recourant, lors des négociations, qu'il désirait engager du personnel stable, puis que le congé soit notifié à l'employé trois mois après qu'il soit transféré en Suisse, n'est certes pas correct, mais il ne rend pas à lui seul le congé abusif (cf. arrêt 4C.234/2001 du 10 décembre 2001, consid. 3b non publié à l'<ref-ruling>, traduit in SJ 2002 I p. 389). Par ailleurs, on ne saurait dire que l'intimée a exercé son droit de résilier sans aucun égard vis-à-vis de son employé (sur l'exigence générale, cf. arrêt 4A_564/2008 du 26 mai 2009 consid. 2.1), le président du conseil d'administration du groupe ayant pris la peine de rencontrer personnellement son employé à Fribourg (avant même la résiliation formelle du contrat) et la maison louée par l'intimée ayant été laissée à disposition du recourant et de sa famille encore huit mois (soit jusqu'au 31 août 2008) après qu'il a été libéré de son obligation de travailler (soit le 31 décembre 2007).
Le grief, dans la mesure où il est recevable, est infondé.
2.4 Le recourant soutient que l'intimée lui a signifié brutalement son congé, ce quelques semaines après son installation et celle de sa famille en Suisse, et sans même tenter de le replacer au sein du groupe. Il se prévaut d'une disproportion grossière entre les intérêts en cause qui rend le congé abusif.
Pour défendre sa thèse, il résume une partie du jugement de première instance et reproduit des extraits d'un procès-verbal d'audience. Il ne se fonde toutefois pas sur les constatations de la juridiction précédente, mais se borne à reprendre, dans les documents résumés, des éléments de faits en sa faveur. Une telle manière de faire n'est pas conforme aux exigences posées par les art. 105 et 106 al. 2 LTF et il s'agit de se fonder uniquement sur les faits établis dans l'arrêt cantonal.
Selon la jurisprudence, il peut y avoir abus de droit en cas de disproportion évidente des intérêts en présence, en particulier lorsque la norme applicable a justement pour but de mettre en place une certaine balance des intérêts. Tel est le cas de l'<ref-law>, dès lors que la résiliation abusive du contrat de travail exprime une limitation légale à la liberté contractuelle de celui qui met fin au contrat, afin de protéger le cocontractant qui a, pour sa part, un intérêt au maintien de ce même contrat. L'idée sous-jacente est avant tout d'offrir une protection sociale au salarié licencié abusivement, dès lors que la protection du congé n'a pas de portée pratique pour l'employeur (ATF <ref-ruling> consid. 4.2 p. 539; ADRIAN STAHELIN, Zürcher Kommentar, 1996, no 4 ad <ref-law> et les auteurs cités).
D'un côté, le recourant a certes reçu son congé quelques mois après son transfert en Suisse (où il avait fait venir sa famille avec l'accord de son employeuse). D'un autre côté, l'employeuse a résilié son contrat de travail en raison d'un changement de stratégie commerciale (dont il n'a pas été établi qu'elle aurait été prévue avant l'arrivée de l'employé en Suisse) de la société intimée, qui amenait celle-ci à licencier plusieurs collaborateurs et à se passer du bureau de vente à Fribourg. Le recourant ne conteste pas valablement, sous l'angle de l'arbitraire (art. 9 Cst.), le lien de causalité (naturelle) existant entre le changement de stratégie de la société et son congé prenant effet au 31 mars 2008 (question de fait: cf. supra consid. 2.2).
On ne saurait dès lors pas affirmer que la protection du congé n'avait aucune portée pratique pour l'employeuse ou que la résiliation serait intervenue par pure convenance personnelle (sur ce cas de figure différent: ATF <ref-ruling> consid. 4.3 p. 541). Retenir l'abus de droit dans les circonstances d'espèce reviendrait à admettre qu'un employé qui accepte de déménager en Suisse avec sa famille pour travailler dans une entreprise active sur le plan international ne saurait être licencié au début de son engagement, même si des impératifs stratégiques commerciaux (en l'occurrence une restructuration) contraignent l'employeur à procéder à des licenciements, et ce, bien que le délai de résiliation prévu dans le contrat ait été respecté (les parties n'ayant pas convenu d'une durée contractuelle minimale). Cette conclusion ne peut être admise. Les conséquences négatives du congé pour l'employé et sa famille - qui est alors retournée en Israël après le 31 août 2008 - ne sont certes pas anodines. Elles relèvent toutefois de la liberté contractuelle et des risques inhérents à la signature d'un contrat de travail du type de celui conclu par les parties; à défaut d'autres circonstances établies par la cour cantonale (qui plaideraient en faveur de l'abus de droit), le mécanisme correcteur de l'<ref-law>, qui présuppose une disproportion évidente des intérêts en présence, ne saurait être mis en oeuvre en l'espèce.
Le grief doit être déclaré mal fondé dans la mesure de sa recevabilité.
3. Il résulte des considérants qui précédent que le recours doit être rejeté dans la mesure où il est recevable.
Les frais et les dépens sont mis à la charge du recourant, qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 3'500 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimée une indemnité de 4'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Ie Cour d'appel civil du Tribunal cantonal de l'Etat de Fribourg.
Lausanne, le 6 juin 2011
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Le Greffier:
Klett Piaget