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.