Faits:
A. Par contrat oral, la société X._ SA (ci-après: l'employeuse), avec siège à Genève, a engagé Y._ (ci-après: l'employé), domicilié en France, en qualité de second de cuisine d'un restaurant exploité à ... (Genève) à compter du 23 janvier 2006.
Le salaire mensuel brut de l'employé a été initialement arrêté à 4'000 fr., porté à 4'700 fr. en mai 2006, puis à 5'000 fr. dès le 1er janvier 2008.
Par lettre du 31 juillet 2008 remise en main propre, A._, agissant au nom de l'employeuse, a licencié Y._ pour le 31 août 2008, en le libérant avec effet immédiat de son obligation de travailler.
L'employé a réclamé sans succès le règlement du solde de ses vacances, la délivrance d'un certificat de travail, le versement d'heures supplémentaires et d'un complément de treizième salaire.
B. Le 11 janvier 2010, l'employé a ouvert action devant le Tribunal des prud'hommes de Genève, concluant à ce que l'employeuse soit condamnée à lui verser le montant de 7'911 fr. correspondant à 40 jours de vacances, 11'166 fr. au titre de complément de treizième salaire et 22'751 fr. pour 2'182 heures supplémentaires, prétention ultérieurement portée à 56'877 fr. 50 pour 1'527,5 heures. Il a également conclu à la délivrance d'un certificat de travail.
L'employeuse s'est opposée à la demande, sous réserve d'un montant chiffré reconnu au titre de treizième salaire.
Des témoins ont été entendus principalement sur les horaires du personnel du restaurant.
Par jugement du 16 novembre 2010, le Tribunal des prud'hommes a condamné l'employeuse à verser à l'employé divers montants en lien avec les postes réclamés pour une somme totale de 41'652 fr. 02, dont 33'148 fr. pour des heures supplémentaires accomplies de fin janvier 2006 à août 2008. La première instance a estimé que l'employé avait effectué une moyenne de dix heures supplémentaires par semaine.
Par arrêt du 9 août 2011, la Chambre des prud'hommes de la Cour d'appel du canton de Genève a annulé le jugement et, statuant à nouveau, condamné l'employeuse à payer à sa partie adverse la somme de 38'807 fr. 30, plus intérêts à 5% l'an dès le 1er septembre 2008, et invité la partie qui en a la charge à opérer les déductions sociales et légales. La cour cantonale a examiné les divers calculs opérés par la première instance et apporté diverses corrections. S'agissant des heures supplémentaires, elle a retenu, fondée sur l'<ref-law> appliqué par analogie, que l'employé avait effectué huit heures supplémentaires par semaine; sur la base des déclarations des témoins, elle a établi qu'il avait pris en moyenne son service le matin à 8h30 jusqu'à 14h00, puis à 17h30 jusqu'à 23h00, avec deux pauses de 30 minutes pour les repas, pour un total quotidien de 10h00, cinq jours par semaine; en moyenne, l'employé a donc travaillé 50 heures par semaine, au lieu de la durée hebdomadaire de travail de 42 heures prévue par l'art. 15 ch. 1 de la convention collective nationale de travail (CCNT) sur l'hôtellerie et la restauration.
C. L'employeuse exerce un recours en matière civile contre l'arrêt cantonal du 9 août 2011. Sous suite de frais et dépens, elle conclut, principalement, à son annulation et à ce que l'employé soit débouté de ses conclusions portant sur les heures supplémentaires (seul point encore litigieux en procédure fédérale), subsidiairement, à l'annulation de l'arrêt entrepris et au renvoi de la cause à l'autorité cantonale. La recourante invoque une violation des art. 42 al. 2, 321 [recte: 321c CO], de l'<ref-law> et elle reproche à l'autorité précédente d'avoir fait preuve d'arbitraire dans l'appréciation des preuves et l'établissement des faits (art. 9 Cst.).

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé dans ses conclusions libératoires (<ref-law>) et dirigé contre un 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. 45 al.1, 46 al. 1 let. b, 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 peut également tenir compte des faits figurant dans la décision de l'autorité inférieure, pour autant que l'arrêt attaqué reprenne au moins implicitement cet état de fait (cf. <ref-ruling> consid. 1, confirmé après l'entrée en vigueur de la LTF notamment par l'arrêt 4A_565/2009 du 21 janvier 2010 consid. 2.2.4). Le Tribunal fédéral 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. 2.4 p. 314; <ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401) - 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>).
En l'espèce, la recourante, aux pages 6 et 7 de son mémoire, relève certains points de fait en renvoyant à diverses pièces du dossier sans toutefois critiquer, sous l'angle de l'arbitraire (art. 9 Cst.), les constatations cantonales. Il n'y a donc pas lieu de s'en écarter.
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. En raison du domicile en France de l'intimé, la cause revêt un caractère international. Le Tribunal fédéral doit examiner d'office la question du droit applicable sur la base du droit international privé suisse en tant que lex fori (<ref-ruling> consid. 2.1 p. 261; <ref-ruling> consid. 2 p. 39, 323 consid. 2.1 p. 327 s.).
En l'espèce, le contrat de travail liant les parties est régi par le droit suisse (<ref-law>).
3. 3.1 La recourante reproche à la cour cantonale d'avoir transgressé l'art. 321 [recte: 321c] CO. Elle se limite à invoquer cette disposition à titre préalable sans fournir une motivation distincte de celle exposée en rapport avec le grief de violation de l'<ref-law>. Il n'y a donc pas lieu d'examiner séparément chacun de ces moyens.
La recourante observe que le juge doit se montrer strict dans le recours à l'<ref-law>. Faisant grief à la cour cantonale d'avoir transgressé cette règle, elle souligne, d'une part, que l'appréciation en équité peut être admise s'il est clairement prouvé, et non seulement rendu vraisemblable, que le travail excédait l'horaire normal dans une mesure déterminable. D'autre part, elle laisse entendre que le travailleur n'a pas fourni de moyens de preuve appropriés, comme des relevés journaliers ou mensuels qui auraient été communiqués à l'employeur.
3.1.1 Lorsqu'il est établi que le salarié a effectué des heures supplémentaires dont il ne parvient pas à prouver le nombre avec exactitude, le juge peut en faire l'estimation en appliquant par analogie l'<ref-law> (arrêt 4C.381/1996 du 20 janvier 1997 consid. 4a non publié à l'<ref-ruling>; arrêt 4C.414/2005 du 29 mars 2006 consid. 5.1; cf. <ref-ruling> consid. 2b p. 276). Dans ce cas, il faut aussi tenir compte de la distinction entre le fait et le droit posée par la jurisprudence en relation avec cette disposition. Il en découle que l'estimation des heures supplémentaires d'après l'<ref-law> repose sur le pouvoir d'apprécier les faits; elle relève donc de la constatation des faits, laquelle ne peut être revue que sous l'angle de l'arbitraire (art. 9 Cst.). Seules constituent des questions de droit le point de savoir quel degré de vraisemblance l'existence d'heures supplémentaires doit atteindre pour justifier l'application de l'<ref-law> et si les faits allégués, en la forme prescrite et en temps utile, permettent de statuer sur la rémunération réclamée en justice (cf. par analogie <ref-ruling> consid. 5.1 p. 364 et les arrêts cités; arrêt 4C.414/2005 du 29 mars 2006 consid. 5.1).
En l'espèce, les deux critiques adressées à la cour cantonale qui visent des questions de droit sont infondées.
3.1.2 S'agissant du degré de conviction requis, la cour cantonale ne laisse pas entendre que les faits allégués par l'employé - soit l'accomplissement des heures supplémentaires réclamées - présenteraient seulement, au regard de divers indices, une certaine vraisemblance; au contraire, après avoir apprécié les preuves versées au dossier, soit les déclarations des témoins, elle arrive à la conclusion que des heures supplémentaires ont "à l'évidence" été effectuées par l'équipe de cuisine (y compris l'intimé). L'autorité cantonale a ainsi jugé que les allégations de l'employé étaient manifestement prouvées et il est patent qu'elle ne s'est pas contentée d'une simple vraisemblance (cf. <ref-ruling> consid. 8a p. 389). On ne saurait lui faire un quelconque reproche à cet égard. Pour le reste, dans la suite de son mémoire, la recourante critique de manière caractéristique l'établissement des faits et l'appréciation des preuves à laquelle s'est livrée la cour cantonale, lorsqu'elle a admis l'existence d'heures supplémentaires et qu'elle les a estimées à huit par semaine (à ce sujet cf. infra consid. 3.2).
3.1.3 S'agissant des moyens de preuve, on ne saurait retenir que seuls les relevés journaliers ou mensuels communiqués à l'employeur peuvent être considérés comme appropriés pour autoriser le juge à apprécier le nombre d'heures supplémentaires en recourant à l'<ref-law>.
Afin de ne pas détourner la règle de preuve résultant de l'<ref-law>, le travailleur doit alléguer et prouver, en tant que cela peut être raisonnablement exigé de lui, toutes les circonstances qui permettent d'apprécier le nombre d'heures supplémentaires exécutées, car la conclusion selon laquelle les heures alléguées ont effectivement été fournies doit s'imposer au juge avec une certaine force (arrêt 4C.141/2006 du 24 août 2006 consid. 4.2.2; arrêt 4C.92/2004 du 13 août 2004 consid. 3.2; arrêt 4P.73/2003 du 18 juillet 2003 consid. 2.3).
Il résulte en l'espèce des constatations cantonales que l'employeuse n'a mis sur pied aucun système de contrôle des horaires; en particulier, elle n'exigeait pas des travailleurs qu'ils établissent des décomptes d'heures (mensuels ou annuels). Cela étant, il est plus difficile pour l'employé d'apporter la preuve requise (cf. arrêt 4P.35/2004 du 20 avril 2004 consid. 3.2 publié in JAR 2005 p. 180) et on ne saurait d'autant moins refuser qu'il utilise un autre moyen pour établir les heures supplémentaires exécutées dans l'intérêt de l'employeuse.
En l'occurrence, en établissant, par des témoignages, son horaire effectif de travail (correspondant aux heures de service de la cuisine), et en indiquant la durée moyenne de 42 heures prévue dans la CCNT, il est indéniable que l'employé a utilisé un moyen de preuve adéquat et prouvé les circonstances qui permettent d'apprécier le nombre d'heures supplémentaires effectuées (cf. sur un cas de figure similaire: arrêt 4A_46/2008 du 30 avril 2008 consid. 2.4).
Les moyens invoqués, et motivés sous l'angle de l'<ref-law>, sont dès lors infondés.
S'agissant de la violation de l'<ref-law>, brièvement invoquée dans le mémoire, force est d'admettre que la recourante n'établit pas dans quelle mesure cette disposition aurait été violée par les magistrats cantonaux. Le moyen est irrecevable.
3.2 La recourante soutient que c'est en appréciant les preuves de manière arbitraire (art. 9 Cst.) que la cour cantonale a retenu que l'intimé a travaillé dix heures par jour, pauses non comprises, cinq jours par semaine.
En matière d'appréciation des preuves et d'établissement des faits, le juge dispose d'un large pouvoir d'appréciation; il n'y a arbitraire que lorsqu'il ne prend pas en compte, sans aucune raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'il se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, il en tire des constatations insoutenables (<ref-ruling> consid. 2.1 p. 9).
La recourante soutient que, contrairement à l'affirmation de l'intimé, celui-ci ne débutait pas son travail à 8h00. Observant que certains témoins ont déclaré que l'employé n'arrivait qu'entre 8h30 et 9h00, elle en conclut qu'il ne commençait son service qu'à 9h00. En définitive, pour contester l'horaire journalier établi par la cour cantonale, la recourante se limite à revenir sur la façon dont cette dernière a apprécié les témoignages et elle tente d'en extraire les éléments plaidant en faveur de sa thèse. Cela n'équivaut pas à démontrer l'arbitraire. S'agissant plus particulièrement de l'heure à laquelle l'intimé débutait son activité, il faut observer que la cour cantonale n'a pas repris telle quelle l'heure alléguée par l'employé puisqu'elle a retenu que celui-ci commençait sa journée de travail à 8h30. Le fait que le témoin B._, exerçant une activité de serveuse à temps partiel dans le restaurant, ait déclaré que le travailleur arrivait entre 8h30 et 9h00 ne permet pas de conclure que la cour cantonale a apprécié les preuves de façon insoutenable; d'une part, l'heure retenue se situe dans le cadre de la fourchette indiquée par B._ et, d'autre part, le témoin D._ (engagé en qualité de cuisinier) a, lui, précisé que l'intimé commençait bien son travail à 8h30.
La recourante soutient encore que, contrairement à l'allégation de l'intimé, celui-ci ne finissait pas sa matinée à 14h30. Elle admet elle-même, en relevant les déclarations des divers témoins, que les cuisiniers partaient en principe à 14h00. Or, c'est précisément cette heure-là que la cour cantonale a retenu comme heure de fin de service. La critique est infondée.
Quant à l'heure de début du service en soirée (17h30 selon l'autorité précédente), la recourante estime qu'elle devait être fixée à 18h00. Dans la mesure où l'autorité précédente ne s'est pas écartée de la fourchette (entre 17h30 et 18h00) évoquée par certains témoins, on ne voit pas qu'elle ait sombré dans l'arbitraire en fixant le début de l'horaire du soir à 17h30, ce d'autant plus que l'heure précise finalement retenue a été affirmée clairement par le témoin D._.
Enfin, la cour précédente a retenu que l'employé finissait son service à 23h00. On ne saurait lui reprocher une appréciation insoutenable pour la seule raison que le témoin C._ (engagé en qualité de responsable de salle) a affirmé que le service du soir se finissait à 22h00; en effet, d'autres témoins (E._, chef de cuisine, et B._) ont affirmé que les cuisiniers quittaient l'établissement à 23h00, voire même plus tard, parfois à minuit.
La recourante n'allègue en outre pas et, encore moins, n'établit que le décompte retenu par la cour cantonale serait en contradiction manifeste avec d'autres moyens de preuve figurant au dossier.
Le grief est infondé.
3.3 S'agissant de la question de la compensation des heures supplémentaires, il faut d'emblée observer que la recourante s'écarte des constatations cantonales lorsqu'elle affirme, sans toutefois fournir une motivation répondant aux exigences strictes des art. 105 al. 2 et 106 al. 2 LTF, que l'intimé ne s'est jamais plaint auprès d'elle de l'impossibilité de compenser les heures supplémentaires. Il résulte en effet des constatations cantonales que l'employé s'est plaint à son supérieur hiérarchique (soit le chef de cuisine) à ce propos, sans succès (jugement de première instance, p. 13, auquel l'arrêt cantonal renvoie implicitement), et qu'il a même expressément attiré l'attention de A._ sur ce point (arrêt entrepris p. 2).
Enfin, la recourante considère que la cour cantonale a écarté arbitrairement la déposition du témoin C._ qui a indiqué qu'en cuisine, de même qu'en salle, lorsque des heures supplémentaires étaient effectuées, elles étaient compensées par des heures en moins sur la journée ou par des congés en plus.
Le moyen est infondé. Il a été établi que l'équipe de cuisine n'a pas eu la possibilité de recourir à des remplaçants, ce qui, logiquement, aurait été nécessaire pour accorder des congés aux membres de l'équipe. Il n'était donc pas insoutenable de conclure que le témoignage de C._ ne suffisait pas à démontrer que du repos compensatoire a été offert à la cuisine par le biais d'auxiliaires, comme l'a prétendu la recourante. Il ressort au demeurant clairement de l'arrêt cantonal que le témoin D._ a affirmé que chacun des employés faisait des heures supplémentaires qui n'étaient pas compensées par du repos.
4. 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 judiciaires sont mis à la charge de la recourante, qui succombe (<ref-law>). Il n'y a pas lieu d'allouer de dépens à l'intimée, qui n'a pas été invitée à déposer une réponse.

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 à 2'000 fr., sont mis à la charge de la recourante.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué aux parties et à la Chambre des prud'hommes du canton de Genève, Cour d'appel.
Lausanne, le 17 octobre 2011
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Piaget