Faits :
A.
A.a. Ressortissante serbe née en 1979, A._ a épousé, le 23 novembre 1997 à E._ (Serbie) son cousin, C_. Trois enfants sont nés de cette union. Le divorce a été prononcé le 27 novembre 2006, l'autorité parentale sur les trois enfants étant attribuée à la mère.
Le 30 novembre 2006, C._ a épousé en Serbie D._, la grand-mère de A._, titulaire d'une autorisation d'établissement en Suisse et vivant à F._ (VS). C._ a demandé en vain à pouvoir rejoindre son épouse en Suisse. Après avoir refusé l'autorisation d'entrée requise le 29 septembre 2008, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a déclaré une première demande de reconsidération irrecevable le 22 juillet 2010 et rejeté la seconde le 20 mai 2014.
A.b. A._ est venue une première fois en Suisse en 2005 pour y trouver du travail, mais sans succès. Elle est revenue en juillet 2006 et a travaillé illégalement en qualité d'ouvrière agricole. Interpellée par la police, elle a été mise en détention en raison de la fausse identité qu'elle avait donnée et a été renvoyée à Belgrade le 15 juillet 2006. Elle a fait l'objet d'une interdiction d'entrée sur le territoire suisse valable jusqu'au 12 juillet 2006 (recte : 2009).
Le 9 octobre 2012, A._ a déposé une demande de visa auprès de l'Ambassade de Suisse à Belgrade en vue d'obtenir une autorisation d'entrée en Suisse pour se marier avec B.X._, ressortissant serbe né le 2 mai 1956, au bénéfice d'une autorisation d'établissement et domicilié à Martigny (VS).
B.
Par décision du 1er octobre 2013, le Service cantonal a rejeté la demande d'autorisation d'entrée en Suisse en vue de mariage présentée par A._ (divorcée de C._), estimant que plusieurs éléments démontraient l'existence d'un mariage de complaisance. Le recours formé par l'intéressée auprès du Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) a été rejeté par décision du 25 mars 2015.
A._ a recouru auprès du Tribunal cantonal du canton du Valais (ci-après: le Tribunal c antonal) qui, par arrêt du 14 août 2015, a admis le recours, annulé la décision attaquée et renvoyé l'affaire au Service cantonal "pour nouvelle décision au sens du consid. 4.4". Dans ce considérant, les juges cantonaux ont, en substance, procédé à une appréciation différente des indices sur lesquels les autorités précédentes s'étaient fondées pour retenir l'existence d'un mariage de complaisance. Ils ont non seulement fortement relativisé ces indices, mais ont aussi pris en compte le fait que le couple formé par A._ et B.X._ s'était marié en Serbie le 12 août 2014 et que plusieurs éléments au dossier attestaient de la réalité et de l'intensité des liens entre les époux.
C.
A l'encontre de l'arrêt du 14 août 2015, le Secrétariat d'Etat aux migrations (SEM) forme un recours en matière de droit public au Tribunal fédéral en concluant formellement à l'annulation " de la décision du 2 juin 2015 rendue par la Chambre administrative de la Cour de justice de la République et canton de Genève ".
Le Conseil d'Etat, se référant à sa décision du 30 mars 2015 [recte: du 25 mars 2015, notifiée le 30 mars 2015] et au recours du SEM, conclut à l'admission du recours et à l'annulation de l'arrêt du 14 août 2015. Au terme de ses déterminations, le Service cantonal propose d'admettre le recours. Dans sa réponse, l'intimée propose le rejet du recours avec suite de frais et dépens.

Considérant en droit :
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit. Selon la jurisprudence, il suffit qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas (cf. <ref-ruling> consid. 2.5 p. 315; <ref-ruling> consid. 1.1 p. 179). En l'espèce, il ressort de l'arrêt attaqué que l'intimée s'est mariée en août 2014 en Serbie, avec un citoyen serbe titulaire d'une autorisation d'établissement en Suisse. Elle jouit partant d'un droit potentiel à séjourner en Suisse (cf. art. 43 LEtr). Le SEM peut ainsi en principe introduire un recours en matière de droit public afin de contester l'arrêt cantonal qui reconnaît l'existence d'un tel droit à une autorisation à l'intimée (cf. <ref-ruling> consid. 1.2 p. 141; arrêt 2C_280/2014 du 22 août 2014 consid. 1.3).
1.2. L'arrêt attaqué renvoie la cause au Service cantonal en lui enjoignant d'octroyer à l'intimée une autorisation de séjour, sans lui laisser de marge de manoeuvre. Il doit partant être qualifié de décision finale au sens de l'<ref-law> (<ref-ruling> consid. 1.1 p. 20; <ref-ruling> consid. 1.3 p. 127), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Le recours a au surplus été déposé en temps utile (<ref-law>) par le SEM qui a qualité pour recourir devant le Tribunal fédéral (cf. <ref-law> en lien avec art. 14 al. 2 de l'ordonnance fédérale du 17 novembre 1999 sur l'organisation du Département fédéral de justice et police (Org DFJP; RS 172.213.1), dans le domaine du droit des étrangers (cf. <ref-ruling> consid. 4.3 p. 542 s.; <ref-ruling> consid. 2.1 p. 46).
1.3. S'agissant des conclusions (cf. <ref-law>), le recours laisse à désirer. Le SEM non seulement se trompe sur la décision dont il demande l'annulation, se référant à une décision rendue par la justice genevoise le 2 juin 2015, mais il se limite aussi à cette annulation, perdant de vue que le Tribunal fédéral a une compétence réformatoire et qu'il lui appartient donc de statuer lui-même sur le fond (<ref-law>; cf. aussi arrêt 2C_356/2014 du 27 août 2014 consid. 1.1 et 5). Dès lors que les conclusions doivent être interprétées selon le principe de la confiance, à la lumière de la motivation (arrêts 2C_123/2014 du 30 septembre 2015 consid. 2.2; 4A_375/2012 du 20 novembre 2012 consid. 1.2, non publié in <ref-ruling>), il n'y a toutefois pas lieu de déclarer le recours irrecevable pour ces motifs. En effet, il ressort de la motivation que le SEM s'en prend à l'arrêt du 14 août 2015 rendu par le Tribunal cantonal du canton du Valais et qu'il demande que l'autorisation de séjour requise soit refusée à l'intimée. Il convient partant d'entrer en matière.
2.
Le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ceux-ci n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (cf. <ref-ruling> consid. 7.1 p. 51; <ref-ruling> consid. 4.2 p. 560) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué (<ref-ruling> consid. 5.2.2 p. 322; <ref-ruling> consid. 6.2 p. 288). En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (cf. <ref-ruling> consid. 5.1 p. 356; <ref-ruling> consid. 3 p. 104; <ref-ruling> consid. 5.2.2 p. 322). Le SEM formule une argumentation qui s'écarte largement de ces principes, comme il le sera vu ci-après.
3.
Initialement, la contestation portait sur l'obtention d'une autorisation d'entrée en Suisse déposée par l'intimée en vue de pouvoir venir s'y marier avec B.X._, que le Service cantonal a refusée le 1er octobre 2013. Il ressort toutefois des constatations cantonales que, postérieurement à cette décision de refus, l'intimée s'est mariée en Serbie avec son fiancé, en août 2014. Cette circonstance implique que la procédure concernant l'octroi d'une autorisation de séjour en vue du mariage en Suisse est devenue sans objet dès cette date. Les autorités cantonales auraient donc pu le constater et mettre fin à la procédure (cf. arrêt 2C_961/2013 du 29 avril 2014 consid. 3.5). Tel n'a toutefois pas été le cas. Dans l'arrêt attaqué, le Tribunal cantonal est entré en matière sur le fond et a raisonné en tenant compte non seulement du mariage subséquent, mais du fait que les époux vivaient désormais ensemble lorsqu'ils séjournaient dans le même pays, écartant pour ces motifs notamment l'existence d'un mariage fictif. Ce faisant, les juges cantonaux ont implicitement modifié l'objet de la contestation initiale en se prononçant désormais non plus sur la possibilité pour l'intimée de pouvoir venir en Suisse pour s'y marier, mais sur l'obtention d'une autorisation de séjour pour vivre auprès de son mari. Le SEM du reste ne s'y est pas trompé, puisqu'il invoque lui-même une violation de l'art. 43 LEtr dans son recours. Il ne se plaint en outre pas de la modification de l'objet du litige en cours de procédure, pas plus que l'intimée. Dans ces circonstances et dès lors que la question juridique soulevée, à savoir l'existence d'un mariage fictif, est la même dans les deux hypothèses, il serait contraire à l'économie de la procédure d'annuler l'arrêt attaqué pour ce motif. Partant, la Cour de céans examinera si le Tribunal cantonal a violé le droit fédéral en refusant d'admettre l'existence d'un mariage de complaisance, ce qui implique,
en cas de rejet du recours, le renvoi à l'autorité cantonale pour qu'elle octroie à l'intimée une autorisation de séjour.
4.
4.1. Aux termes de l'art. 43 al. 1 LEtr, le conjoint étranger du titulaire d'une autorisation d'établissement ainsi que ses enfants célibataires étrangers de moins de 18 ans ont droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité, à condition de vivre en ménage commun avec lui. La recourante, en tant qu'épouse d'un étranger titulaire d'une autorisation d'établissement, a donc a priori droit à une autorisation de séjour sur la base de cette disposition.
4.2. L'art. 51 al. 2 let. a LEtr prévoit toutefois que les droits prévus à l'art. 43 LEtr s'éteignent s'ils sont invoqués abusivement. Les mariages fictifs ou abusifs sont visés par cette disposition (cf. arrêts 2C_310/2014 du 25 novembre 2014 consid. 2.1; 2C_804/2013 du 3 avril 2014 consid. 2.1). Selon la jurisprudence, il y a mariage fictif lorsque celui-ci est contracté dans le seul but d'éluder les dispositions de la loi fédérale sur les étrangers, en ce sens que les époux (voire seulement l'un d'eux) n'ont jamais eu la volonté de former une véritable communauté conjugale (cf. <ref-ruling> consid. 4a p. 55; arrêts 2C_177/2013 du 6 juin 2013 consid. 3.2; 2C_222/2008 du 31 octobre 2008 consid. 3.3 in fine et 4.3). Toute la difficulté réside dans la circonstance que l'intention réelle des époux ne peut souvent pas être établie par une preuve directe, mais seulement grâce à des indices (cf. <ref-ruling> consid. 5a p. 57; arrêts 2C_804/2013 du 3 avril 2014 consid. 2.2; 2C_177/2013 du 6 juin 2013 consid. 3.2).
Constituent notamment les indices d'un mariage fictif: le fait que l'époux étranger soit menacé d'un renvoi ou ne puisse obtenir une autorisation de séjour autrement que par un mariage; l'existence d'une sensible différence d'âge entre les époux; les circonstances particulières de leur rencontre et de leur relation, tels une courte période de fréquentation avant le mariage ou le peu de connaissances que les époux ont l'un de l'autre, etc. (cf. notamment <ref-ruling> consid. 2b p. 295; arrêt 2C_177/2013 du 6 juin 2013 consid. 3.3 et les arrêts cités).
La preuve d'un mariage fictif doit être apportée par l'autorité, sous réserve de l'obligation des parties de collaborer à l'établissement des faits. Cette obligation des parties est d'autant plus grande que les circonstances objectives du cas permettent de douter de la réelle et commune volonté des époux de former une communauté de vie (arrêt 2C_587/2008 du 4 décembre 2008 consid. 4.1). En présence d'indices sérieux d'un mariage fictif, il appartient aux parties de démontrer, par une argumentation circonstanciée, l'existence d'une relation conjugale réellement vécue et voulue (arrêts 2C_177/2013 du 6 juin 2013 consid. 3.4; 2C_222/2008 du 31 octobre 2008 consid. 3.2).
Les constatations portant sur les indices peuvent concerner des circonstances externes tout comme des éléments d'ordre psychique relevant de la volonté interne (volonté de chacun des époux). Il s'agit, dans les deux cas, de constatations de fait (<ref-ruling> consid. 2.3 p. 152 et les arrêts cités) qui lient le Tribunal fédéral (<ref-law>), sauf si elles ont été établies de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (cf. consid. 2 supra). En revanche, le Tribunal fédéral examine librement si les constatations de fait (indices) permettent de conclure à l'existence d'un mariage fictif.
5.
Invoquant une violation des art. 43 al. 1 et 51 al. 2 let. a LEtr, le SEM affirme, contrairement à la position soutenue dans l'arrêt attaqué, que, sur le vu des indices du cas d'espèce, il n'existait pas de réelle volonté de fonder une communauté conjugale, de sorte que l'intéressée a invoqué abusivement les règles sur le regroupement familial.
5.1. Le Tribunal cantonal s'est écarté de la position des autorités administratives valaisannes qui avaient reconnu l'existence d'un mariage de complaisance, sur la base d'une argumentation circonstanciée. Les juges ont tout d'abord relativisé la portée de certains indices, appréciant différemment les faits que les autorités administratives. Tout en admettant qu'il était curieux que l'époux ne se souvienne que de l'année, mais pas du mois de sa première rencontre avec l'intimée, ils ont constaté que les versions des époux quant aux périodes de séjour commun n'étaient pas si discordantes; ils ont partant admis que les fiancés avaient une liaison suivie depuis 2010 et qu'ils avaient vécu ensemble certaines périodes en 2011 et en 2012. Le fait que l'intimée n'ait pas indiqué qu'elle voyait son fiancé dans sa maison à E._, mais dans des cafés et des restaurants s'expliquait parce que sa famille désapprouvait son attitude et que vivre ensemble hors mariage était considéré comme déshonorant dans les pays balkaniques. Quant au rapport de la police intercommunale de G._ sur lequel le Conseil d'Etat s'était fondé pour affirmer que la recourante avait menti, il a été écarté par le Tribunal cantonal, car il reposait sur une dénonciation anonyme effectuée dans le cadre d'une affaire concernant une autre personne et il contenait des propos indirects, ainsi que des éléments infirmés par les actes au dossier. Le fait que les époux se soient mariés en Serbie le 12 août 2014 tempérait également sensiblement les autres éléments, tels la différence d'âge, le fait que l'épouse ait tu son séjour illégal en Suisse, le rejet de leur union par leurs proches ou les imprécisions ou mensonges de l'intimée.
Les juges cantonaux ont en outre tenu compte d'autres indices démontrant la réalité de l'union conjugale, comme la bonne connaissance réciproque du couple, la relation suivie et les contacts réguliers entre eux depuis leur rencontre en 2010, concrétisée par leur mariage en 2014, sur la proposition de l'époux et enfin leur projet commun de vivre ensemble en Suisse et d'y fonder si possible une famille. Enfin, l'arrêt attaqué constate que la réalité et l'intensité des liens du couple étaient attestées par plusieurs pièces au dossier, tels des photographies, des témoignages écrits et leur domicile commun en Suisse lorsque l'intimée venait dans le pays.
5.2. Le SEM conteste la position du Tribunal cantonal. L'essentiel de son argumentation consiste toutefois à discuter les éléments de fait retenus et leur appréciation, opposant sa propre version et interprétation des faits figurant dans l'arrêt attaqué. Ce faisant, le SEM oublie que le Tribunal fédéral n'est pas une juridiction d'appel et que les critiques appellatoires n'ont pas leur place dans la procédure régie par la LTF (cf. consid. 2 supra). Pour que la Cour de céans puisse revoir les faits, il aurait appartenu au SEM d'invoquer l'arbitraire ou la constatation manifestement inexacte des faits et d'expliquer en quoi l'arrêt attaqué, en omettant ou au contraire en prenant en compte certains éléments de fait, serait parvenu à un résultat arbitraire ou insoutenable.
Le recours n'y procède nullement. Par exemple, le SEM reproche aux juges de ne pas avoir tenu compte des déclarations figurant dans le rapport de police de G._, en faisant fi des explications, pourtant convaincantes données par le Tribunal cantonal pour écarter ce moyen de preuve (dénonciation anonyme dans une autre procédure; propos indirects et infirmés par des actes au dossier). Il en va de même lorsque le SEM s'en prend à la constatation des juges selon laquelle les réponses apportées par le couple étaient généralement concordantes et dénotaient une bonne connaissance réciproque, en opposant sa propre appréciation des réponses fournies, perdant de vue que seule une appréciation arbitraire pourrait être corrigée. Tel est aussi le cas lorsque le SEM remet en cause les témoignages qui mentionnent une relation nourrie et durable du couple, retenant qu' "à son sens", ces témoignages ne suffisent pas. De telles critiques ne sont pas recevables et ne permettent en tous les cas pas à la Cour de céans de s'écarter des faits constatés (cf. <ref-law>).
5.3. Ce n'est que dans la faible mesure où le SEM reproche au Tribunal cantonal de n'avoir pas suffisamment tenu compte d'indices figurant dans l'arrêt attaqué et plaidant pour l'existence d'un mariage fictif qu'il convient d'entrer en matière. Ces indices consistent dans le comportement de l'ancien mari de l'intimée, qui avait épousé la grand-mère de celle-ci et avait cherché en vain à venir vivre en Suisse, dans la différence d'âge entre les intéressés, l'intimée ayant 23 ans de moins que son époux, dans les courtes périodes de vie commune du couple et dans le fait que ce mariage était le seul moyen pour l'intimée de séjourner en Suisse et d'y travailler. Certes, ces indices plaident en faveur d'un mariage fictif. Toutefois, comme l'a retenu pertinemment le Tribunal cantonal (cf. consid. 5.1 supra), ces indices sont contredits par d'autres éléments qui démontrent une union réelle du couple. Ainsi, les époux, qui ont fait connaissance en 2010, se sont mariés en 2014, vivent désormais ensemble lorsqu'ils séjournent dans le même pays, et, toujours selon les constatations cantonales, nourrissent une relation intense, attestée par des photographies et des témoignages. Sur la base de l'ensemble de ces éléments, on ne voit pas que l'on puisse reprocher au Tribunal cantonal d'avoir violé le droit fédéral en considérant que les éléments en faveur d'une union vécue l'emportaient sur le comportement de l'ex-mari de l'intimée, sur la différence d'âge entre les époux et sur quelques imprécisions dans les déclarations des intéressés.
5.4. Dans ces circonstances, le recours ne peut qu'être rejeté, dans la faible mesure où l'on peut considérer qu'il est recevable.
6.
Compte tenu de l'issue du litige, il sera statué sans frais (cf. <ref-law>). La Confédération, soit pour elle le SEM, versera en revanche des dépens à l'intimée, qui a fourni une réponse au recours par l'entremise de son avocat (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le Secrétariat d'Etat aux migrations versera à l'intimée une indemnité de 2'000 fr. à titre de dépens.
4.
Le présent arrêt est communiqué au Secrétariat d'Etat aux migrations, au mandataire de l'intimée, au Service de la population et des migrations, au Conseil d'Etat ainsi qu'au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 6 janvier 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Zünd
Le Greffier : Chatton