Faits :
A.
Le 7 mars 2014, B._, ressortissant sénégalais né en 1974 et domicilié à Dakar (Sénégal), a déposé auprès de l'Ambassade de Suisse à Dakar (ci-après: l'Ambassade) une autorisation d'entrée en Suisse pour vivre auprès de A._, ressortissante suisse née en 1980, qu'il avait épousée à Dakar le 1er mars 2014.
A la demande du Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal), l'Ambassade a entendu B._ le 16 juillet 2014, tandis que la police municipale de X._ (VS) a auditionné A._ le 28 juillet 2014 au sujet du couple et des circonstances du mariage. Il ressort, notamment, de ces déclarations que A._ et B._ s'étaient rencontrés sur l'île espagnole de Y._ le 11 juillet 2011, où l'intéressée et sa soeur faisaient des vacances, tandis que l'intéressé, résidant clandestin, vendait des lunettes et des montres dans les restaurants.
B.
Par décision du 14 novembre 2014, le Service cantonal a rejeté la demande d'autorisation d'entrée et de séjour en Suisse présentée par B._, au motif que des indices portaient à croire que le mariage était fictif et visait en réalité à obtenir pour l'époux une autorisation de séjour en Suisse. Saisi d'un recours des époux contre cette décision, le Conseil d'Etat du canton du Valais l'a rejeté par décision du 17 juin 2015. Les époux ont formé recours contre cette décision auprès de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal), qui l'a rejeté par arrêt du 23 octobre 2015.
C.
Agissant par la voie du recours en matière de droit public devant le Tribunal fédéral, A._ et B._ concluent, sous suite de frais et dépens, principalement, à l'annulation de l'arrêt du 23 octobre 2015 et à l'octroi d'une autorisation d'entrée et de séjour en Suisse en faveur de B._; subsidiairement, au renvoi de la cause au Tribunal cantonal pour que celui-ci auditionne l'époux et rende un nouvel arrêt.
Le Tribunal cantonal et le Service cantonal renoncent à présenter des observations. Faisant siens les considérants de l'arrêt attaqué, le Conseil d'Etat conclut au rejet du recours dans la mesure de sa recevabilité. Le Secrétariat d'Etat aux migrations propose le rejet du recours. Dans sa réplique du 5 avril 2016, les recourants ont maintenu les conclusions de leur recours.

Considérant en droit :
1.
D'après l'art. 83 let. c ch. 2 LTF (RS 173.110), le recours en matière de droit public est irrecevable contre les décisions dans le domaine du droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Selon la jurisprudence, il suffit, sous l'angle de la recevabilité, qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et que, partant, la voie du recours en matière de droit public soit ouverte (cf. <ref-ruling> consid. 1.1 p. 179). A._ (ci-après: la recourante) et B._ (ci-après: le recourant) fondent le droit du second à une autorisation sur l'art. 42 al. 1 LEtr (RS 142.20), du fait du mariage du recourant avec une Suissesse. Ils invoquent en outre le droit au respect de la vie familiale (art. 8 CEDH [RS 0.101] et art. 13 Cst. [RS 101]), en demandant à pouvoir mener une relation de couple effective en Suisse. Ces circonstances sont potentiellement de nature à conférer un droit à une autorisation de séjour en faveur du recourant. Il s'ensuit que le recours est recevable sous l'angle de l'art. 83 let. c ch. 2 LTF, étant précisé que le point de savoir si le recourant dispose effectivement d'un tel droit relève du fond et non de la recevabilité (cf. <ref-ruling> consid. 1.1 p. 179; arrêt 2C_555/2015 du 21 décembre 2015 consid. 1.1). Pour le surplus, l'arrêt attaqué est une décision finale (cf. <ref-law>), rendue en dernière instance cantonale par un Tribunal supérieur (cf. art. 86 al. 1 let. d et al. 2 LTF). Déposé en temps utile (cf. <ref-law>) et dans les formes requises (cf. <ref-law>) par les destinataires de l'arrêt attaqué qui ont qualité pour recourir au sens de l'<ref-law>, le recours en matière de droit public est par conséquent recevable.
2.
Saisi d'un recours en matière de droit public, le Tribunal fédéral applique d'office le droit fédéral (<ref-law>), qui comprend les droits de nature constitutionnelle (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Toutefois, à moins que la décision entreprise ne contienne des vices juridiques manifestes, le Tribunal fédéral s'en tient aux arguments juridiques soulevés dans le recours (cf. art. 42 al. 1 et 2 LTF; <ref-ruling> consid. 2.2.1 p. 389; arrêt 2C_91/2015 du 31 mai 2016 consid. 2.1, non destiné à la publication).
3.
3.1. Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, les recourants se plaignent d'une violation de leur droit d'être entendus. Ils font valoir que le procès-verbal de l'audition du recourant du 16 juillet 2014 par l'Ambassade, dont le Tribunal cantonal a déduit certains indices de l'existence d'un mariage de complaisance, n'avait pas été relu ni signé par l'intéressé, alors même que l'audition s'était déroulée dans sa langue maternelle, le wolof, mais avait été verbalisée en français; ce n'était que tardivement que le recourant s'était aperçu d'une traduction incorrecte de ses déclarations. Le procès-verbal n'arborait de plus aucune référence à l'Ambassade, de sorte qu'on pouvait douter de son caractère officiel. Le Tribunal cantonal n'aurait partant pas dû tenir compte de ce procès-verbal vicié et il fallait renvoyer la cause au Tribunal cantonal pour qu'il procède à une (nouvelle) audition du recourant.
Dans l'arrêt entrepris, le Tribunal cantonal a jugé que le procès-verbal du 16 juillet 2014 contenait la déposition complète du recourant et était donc valable sous cet angle. De plus, aucune base légale applicable n'imposait la signature de ce document par l'intéressé. Par ailleurs, le recourant maîtrisait la langue française dans laquelle le procès-verbal avait été traduit. Même à supposer que ce document fût frappé d'une irrégularité formelle, le recourant avait pu valablement recourir, en exposant son point de vue, et n'avait donc subi aucun préjudice.
3.2. Compris comme l'un des aspects de la notion générale de procès équitable au sens de l'art. 29 Cst., le droit d'être entendu (art. 29 al. 2 Cst.) garantit notamment le droit pour l'intéressé de prendre connaissance du dossier, de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 6.3.1 p. 299; arrêts 5A_750/2015 du 4 mars 2016 consid. 2.1; 2C_782/2015 du 19 janvier 2016 consid. 3.1).
Le droit d'être entendu impose également aux autorités un devoir général de tenue des dossiers, qui confère aux parties le droit d'obtenir que leurs déclarations, celles de témoins ou d'experts ou d'autres actes d'instruction importants pour l'issue du litige soient consignés dans un procès-verbal, tout au moins dans leur teneur essentielle (cf. <ref-ruling> consid. 2.2 et 2.3 p. 89 ss; <ref-ruling> consid. 4.1 s p. 477; <ref-ruling> consid. 2a p. 16 s.; arrêts 5A_945/2015 du 7 juillet 2016 consid. 3.5, non destiné à la publication). Ces principes, dégagés dans le cadre des procédures judiciaires, sont transposables aux procédures administratives de première instance concernant l'octroi ou le renouvellement d'une autorisation de séjour (cf. MICHELE ALBERTINI, Der verfassungsmässige Anspruch auf rechtliches Gehör im Verwaltungsverfahren des modernen Staates, thèse Berne, 2000, p. 257 s.). En revanche, à moins qu'une norme topique ne prévoie une telle exigence spécifique, le défaut de signature d'un procès-verbal ne fait pas de celui-ci un moyen de preuve inexploitable (cf., en droit des assurances sociales, arrêt de l'ancien Tribunal fédéral des assurances U 61/06 du 19 septembre 2006 consid. 1.3.4).
3.3. C'est à tort que les recourants mettent en doute l'authenticité du procès-verbal dressé par l'Ambassade: tel qu'il ressort du dossier cantonal (<ref-law>), l'audition du recourant a en effet eu lieu sur requête du Service cantonal à l'Ambassade (cf. courrier du 8 juillet 2014, en p. 25 du dossier cantonal) et les réponses fournies par l'intéressé dans le cadre de son audition du 16 juillet 2014 ont été accompagnées d'une fiche officielle et signée de l'Ambassade du 30 juillet 2014 (cf. p. 38 du dossier cantonal).
Par ailleurs, il n'apparaît pas que le droit de procédure cantonal offre aux recourants une protection plus étendue que l'art. 29 al. 2 Cst. (cf., sur cette hypothèse, <ref-ruling> consid. 2.4.2.1 p. 96; arrêt 2C_1073/2014 du 28 juillet 2015 consid. 3.3.4), en ce sens que la validité ou régularité des procès-verbaux établis par l'autorité administrative dépendrait de la signature de la personne auditionnée. Le renvoi que l'art. 18a al. 4 de la loi valaisanne sur la procédure et la juridiction administratives du 6 octobre 1976 (LPJA/VS; RS/VS 172.6) opère aux dispositions du CPC (RS 272), dont l'art. 176 al. 1, invoqué par les recourants, impose certes la lecture et la signature du procès-verbal par les témoins, se limite expressément à la procédure devant le Tribunal cantonal, l'audition par l'autorité administrative étant réglementée de façon plus vague à l'al. 1 de l'art. 18a LPJA. A supposer que la PA (RS 172.021; cf. notamment <ref-law>) régisse l'audition du recourant accomplie par l'Ambassade à la demande du Service cantonal, en conformité avec l'art. 44 al. 2 Cst. (cf., pour l'entraide administrative, <ref-law> [RS 273] cum <ref-law> et art. 35 de l'ordonnance sur l'entrée et l'octroi de visas du 22 octobre 2008 [OEV; RS 142.204]; voir aussi PATRICIA EGLI, Die Bundestreue, thèse St-Gall, 2010, n. 951 ss p. 587 s. et n. 983 p. 606 s.; RAINER J. SCHWEIZER, ad art. 44 Cst., in Die schweizerische Bundesverfassung - St. Galler Kommentar, 3e éd., 2014, n. 25 ss p. 967 ss; WALDMANN/ KRAEMER, ad art. 44 Cst., in Bundesverfassung - Basler Kommentar, 2015, n. 26 p. 866), elle n'exigerait pas non plus la signature des procès-verbaux; le renvoi effectué par l'<ref-law> à certaines dispositions de la PCF n'englobe en effet pas l'art. 7 al. 2 de cette loi imposant la contre-signature des procès-verbaux.
Finalement, en tant que le recourant reproche au Tribunal cantonal d'avoir fondé son arrêt sur une traduction erronée de certaines de ses déclarations auprès de l'Ambassade, dont il a du reste contesté en détail plusieurs points dans ses recours successifs devant le Conseil d'Etat et le Tribunal cantonal, son grief se confond avec celui de l'appréciation arbitraire des preuves par la précédente instance, qu'il soulève également.
3.4. Par conséquent, le grief tiré de la violation du droit d'être entendu doit être écarté.
4.
Se prévalant du principe de l'interdiction de l'arbitraire (art. 9 Cst.), les recourants reprochent aux juges cantonaux d'avoir mal apprécié les faits et les preuves, en particulier la déclaration faite par le recourant auprès de l'Ambassade.
4.1. S'agissant de l'appréciation des preuves et des constatations de fait, il y a arbitraire lorsque l'autorité ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'elle se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, elle en tire des constatations insoutenables (<ref-ruling> consid. 2.3 p. 266; <ref-ruling> consid. 4.1.2 p. 62; arrêt 2D_73/2015 du 30 juin 2016 consid. 3.1). L'appréciation des preuves doit être arbitraire non seulement en ce qui concerne les motifs invoqués par la juridiction cantonale pour écarter un moyen de preuve, mais également dans son résultat (<ref-ruling> consid. 4.3 et 4.3.1 p. 176 s.; <ref-ruling> consid. 2.4 p. 5; arrêt 2C_682/2012 du 7 février 2013 consid. 3.1).
4.2. Dans l'arrêt attaqué, le Tribunal cantonal a souscrit, en examinant chaque élément, à l'analyse effectuée par le Conseil d'Etat, qui a retenu l'existence d'un mariage de complaisance sur la base des indices suivants: la discordance de certaines déclarations des conjoints, le manque de photographies ou de relevés téléphoniques démontrant l'existence de contacts réguliers, la clandestinité dans laquelle avait vécu l'époux en Espagne, l'inactivité de ce dernier au Sénégal, l'absence de vie commune des époux avant le mariage et de points communs entre eux, le fait que, le jour de la cérémonie de mariage au Sénégal, aucun membre de la famille de l'épouse ne se soit déplacé, pas plus que la mère du mari, qui pourtant habitait à Dakar, ainsi que la rapidité avec laquelle était survenu le projet de mariage.
4.3. Dans l'optique de contester cette analyse, les recourants critiquent l'appréciation de différentes preuves effectuée par le Tribunal cantonal.
4.3.1. Les recourants remettent en cause le constat selon lequel l'épouse avait dû consulter son certificat de mariage pour épeler les nom et prénom de son époux, au motif que l'on ne verrait pas "en quoi cela pose problème dans la mesure où le Tribunal [cantonal] lui-même a indiqué que chaque recourant connaît la situation personnelle de l'autre" (recours, p. 17). Un tel argument frôle la témérité et n'est en tout état pas propre à retenir l'arbitraire. Si la précédente juridiction a effectivement établi que chaque recourant connaissait la situation personnelle de l'autre, les recourants omettent de préciser qu'elle avait relativisé la portée de ce point en constatant "leur ignorance sur certains détails importants", notamment sur la façon d'écrire les nom et prénom du conjoint.
4.3.2. Selon les recourants, l'époux se serait manifestement trompé dans sa déclaration quant à la durée du séjour de son épouse au Sénégal. La réponse de deux semaines qu'il avait fournie correspondait, en raison d'un malentendu, à la durée totale des vacances prises par son épouse et non uniquement au séjour de quelques jours à Dakar en vue de la célébration du mariage (recours, p. 17). Or, à la question de l'Ambassade de savoir "pour quelle durée son épouse est (...) déjà allée au Sénégal pour le rencontrer", le recourant avait univoquement répondu " 2 semaines à partir du 28.02.2014 pour le mariage "; il s'était de plus rétracté seulement après avoir été confronté à la réponse donnée par son épouse. Quoi qu'il en soit, il ne suffit pas qu'une interprétation différente des déclarations du recourant soit concevable pour pouvoir qualifier d'arbitraire l'appréciation de celles-ci par les précédents juges.
4.3.3. La même conclusion s'impose lorsque les recourants réinterprètent librement leurs perceptions et déclarations divergentes, respectivement seulement partiellement concordantes au sujet des présents qu'ils se sont offerts en vue du mariage, du nombre de convives - invités ou présents - à leur réception de mariage à Dakar, du nombre et qualité des photographies ou encore de relevés téléphoniques censés démontrer des contacts réguliers entre les époux (recours, p. 17 ss). Même dans l'hypothèse où certains des clichés versés au dossier cantonal illustreraient, contrairement aux constats du Tribunal cantonal, diverses étapes au jour du mariage des époux à Dakar ou leur séjour commun en Espagne, ce que les recourants n'ont cependant pas démontré, on ne voit pas qu'une telle erreur permette de retenir de l'arbitraire, voire de la "mauvaise foi" (recours, p. 18) dans l'appréciation globale des faits à laquelle a procédé le Tribunal cantonal. On précisera, en outre, que les juges cantonaux avaient relativisé le caractère probant des photographies du fait que celles-ci n'étaient pas datées et qu'elles ont été prises avec des personnes "dont rien n'indique qu'elles soient parentes du recourant" (arrêt, p. 10), ce qu'il aurait d'emblée appartenu aux recourants de prouver.
4.3.4. S'agissant des conversations téléphoniques et autres échanges des époux, qui sont censés établir la durée et l'effectivité de leurs liens, le Tribunal cantonal a dûment tenu compte des copies "d'une dizaine de SMS échangés entre eux de septembre à novembre 2014 et en juillet 2015", ainsi que des deux cartes de Noël et d'anniversaire et des deux "attestations sur l'honneur" envoyées par le recourant (arrêt, p. 10). Sans arbitraire, la précédente instance a néanmoins jugé que ces quelques éléments, survenus durant des périodes de temps précises, ne suffisaient pas à étayer le caractère quotidien et intense des communications sur plusieurs années.
4.3.5. Les recourants contestent en outre que le Tribunal cantonal ait retenu, comme indice corroborant un mariage de complaisance, la circonstance que le recourant avait, avant de connaître la recourante, "vécu et travaillé clandestinement plusieurs années en Espagne, qu'il se trouve actuellement sans emploi au Sénégal et que, selon la recourante, qui lui a envoyé 3'000 fr. depuis leur rencontre et avait payé son billet d'avion pour venir au Sénégal depuis l'Espagne, sa mère subviendrait à ses besoins" (arrêt, p. 10). Sans nier ces circonstances, les recourants les estiment dépourvues de pertinence, dès lors que l'intéressé n'avait plus adopté un tel comportement répréhensible depuis qu'il avait fait la connaissance de la recourante (recours, p. 19). A tort. Les éléments litigieux n'ont pas pour but, notamment, d'évaluer la menace que le recourant représenterait pour l'ordre public suisse s'il était autorisé à s'installer auprès de son épouse en Valais; ils sont pertinents pour juger si le mariage des époux peut être ou non considéré comme fictif. Or, sous l'angle de l'interdiction de l'arbitraire, on ne voit pas que les circonstances économiques ou relatives au statut d'étranger ayant précédé la conclusion du mariage avec une Suissesse ne puissent servir comme indices pour un mariage de complaisance, notamment en vue de saisir l'éventuelle motivation de l'étranger à la base du mariage.
4.3.6. D'après les recourants, le Tribunal cantonal a eu tort de retenir que la mère de l'intéressé ne s'était pas rendue à leur mariage à la mairie de Dakar en raison du coût excessif du taxi pour se déplacer à l'autre bout de la ville; l'empêchement résulterait davantage de problèmes de santé de sa mère, qui avait du reste participé au mariage musulman préalable, toutefois célébré en l'absence des parties. Une nouvelle fois, les recourants perdent de vue que leur argumentation donne une explication possible parmi d'autres en vue d'éclairer un élément du dossier, soit l'absence de la mère du recourant à leur mariage, qui a été considérée comme un indice pour le mariage de complaisance des époux. Or, en l'absence de preuves contraires, on ne voit pas en quoi l'appréciation par le Tribunal cantonal eût été arbitraire, d'autant moins, comme l'ont fait remarquer les précédents juges, qu'il aurait dans une telle situation été loisible à l'épouse de rencontrer sa belle-mère à son domicile à Dakar le jour du mariage civil. Le fait que la recourante aurait ultérieurement rencontré la mère et divers autres membres de la famille de son mari ou que ce dernier ait entretenu des contacts téléphoniques avec sa belle-famille en Suisse ne change rien au constat que la mère de l'époux n'était pas présente au mariage qui s'est tenu à Dakar.
4.3.7. Sont pareillement appellatoires, et donc inadmissibles au regard de l'<ref-law>, les arguments des recourants tendant à réinterpréter en leur faveur, notamment en mentionnant l'intolérance de la recourante au "climat sénégalais en raison de ses problèmes de santé" et ses obligations professionnelles, la circonstance qu'aucun membre de la famille de l'épouse n'avait assisté au mariage à Dakar et que les époux n'avaient jamais vécu en commun (cf. recours, p. 20).
4.3.8. On peut certes s'interroger sur le poids attribué par le Tribunal cantonal aux déclarations de la recourante du 28 juillet 2014, selon lesquelles la volonté du recourant de rejoindre son épouse en Suisse serait motivée par son intolérance à la chaleur, l'absence de travail au Sénégal et le souhait d'améliorer ses conditions de vie, dès lors que la recourante avait en même temps souligné que le principal motif de son mariage était d'ordre sentimental (<ref-law>; procès-verbal du 28 juillet 2014, p. 4). En revanche, l'on ne saurait, sous l'angle de l'arbitraire, reprocher aux précédents juges de s'être étonnés du fait que l'épouse, priée par la police de décrire les circonstances avant et pendant le mariage, n'avait pas mentionné la célébration de son mariage coutumier avec le recourant; elle avait en outre déclaré qu'il n'y avait pas eu de fiançailles avant le mariage. La version de la recourante, qui a justifié son oubli par l'origine musulmane de la cérémonie coutumière, qu'elle n'assimilait pas à un véritable mariage, n'est pas apte à établir le caractère choquant des déductions tirées par le Tribunal cantonal.
4.3.9. Quant aux autres faits qu'a retenus et appréciés le Tribunal cantonal, notamment ceux en lien avec la réalisation rapide du projet de mariage et la décision de la recourante de rendre visite à sa famille en Italie, et non à son époux, durant ses vacances du 14 au 27 juillet 2014, alors que les époux disaient souffrir au plus haut point de leur séparation, les contestations appellatoires qui figurent en particulier dans les parties "faits" et en droit du mémoire de recours ne permettent pas de les qualifier d'arbitraires.
4.4. Au vu des éléments qui précèdent, le grief tiré de l'établissement arbitraire des faits doit être écarté. La Cour de céans se fondera donc exclusivement sur les faits établis par le Tribunal cantonal (<ref-law>).
5.
Les recourants se prévalent d'une violation des règles sur le regroupement familial, au sens des art. 42 ss LEtr, ainsi que de leur droit au respect de la vie privée et familiale garanti aux art. 13 Cst. et 8 CEDH. En refusant d'octroyer une autorisation de séjour au recourant, alors qu'aucun élément ne permettait de croire que son union avec la recourante était fictive, et en niant l'application de l'art. 8 CEDH à leur situation, au motif que la relation du couple n'était pas étroite et effective et en dépit de contacts réguliers des époux depuis près de quatre ans, le Tribunal cantonal aurait violé les dispositions précitées.
5.1. Selon l'art. 42 LEtr, le conjoint d'un ressortissant suisse a 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. L'art. 51 al. 1 let. a LEtr dispose toutefois que les droits prévus à l'art. 42 s'éteignent s'ils sont invoqués abusivement, notamment pour éluder les dispositions de la présente loi sur l'admission et le séjour ou ses dispositions d'exécution.
Les art. 13 Cst. et 8 CEDH garantissent, entre autres, le droit au respect de la vie privée et familiale. Néanmoins, le mot "famille" englobe la relation née d'un mariage légal et non fictif (arrêts de la Cour EDH Abdulaziz, Cabales et Balkandali c. Royaume-Uni [plénum], du 28 mai 1985, req. 9214/80, 9473/81 et 9474/81, série A94, par. 62; Pini et al. c. Roumanie, du 22 juin 2004, req. 78028/01 et 78030/01, Rec. 2004-IV, par. 143); il suppose donc l'existence d'une relation qui soit étroite et effective avec une personne de la famille ayant le droit de résider durablement en Suisse (cf. <ref-ruling> consid. 1.3 p. 287; <ref-ruling> consid. 1e p. 5; arrêts 2C_1075/2015 du 28 avril 2016 consid. 1.2; 2A.19/1998 du 20 novembre 1998 consid. 5, in RDAT 1999 I 194; PETER UEBERSAX, Der Rechtsmissbrauch im Ausländerrecht, unter Berücksichtigung der Rechtsprechung des Bundesgerichts, in Annuaire du droit de la migration 2005/2006 [Achermann et al. (éd.)], 2006, p. 3 ss, 13).
Il suit de ces dispositions que l'examen des griefs tirés des art. 42 ss LEtr, 13 Cst. et 8 CEDH se confond avec le point de savoir si c'est à bon droit que le Tribunal cantonal a qualifié de mariage de complaisance l'union des recourants.
5.2. Il y a mariage fictif ou de complaisance 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. L'intention réelle des époux est un élément intime qui, par la nature des choses, ne peut guère être établie par une preuve directe, mais seulement grâce à un faisceau d'indices (cf. <ref-ruling> consid. 4a p. 55 et 5a p. 57; arrêt 2C_177/2013 du 6 juin 2013 consid. 3.2). Constituent notamment les indices d'un mariage fictif ou d'un abus de droit les éléments suivants: une grande différence d'âge entre les fiancés, une impossibilité ou de grandes difficultés à communiquer entre eux, une méconnaissance réciproque de leur cadre de vie et de leurs conditions d'existence (famille, amis, profession, hobbies, habitudes, etc.), un arrangement financier en vue du mariage, un projet de mariage élaboré peu de temps après la rencontre des fiancés, une procédure de renvoi en cours contre le fiancé dont le droit de résider en Suisse dépend de la conclusion du mariage, une absence de vie commune des fiancés avant le mariage, l'appartenance de la personne admise à résider en Suisse à un groupe social marginal, etc. (cf. <ref-ruling> consid. 2b p. 295; arrêts 2C_566/2013 du 2 décembre 2013 consid. 3.3; 2C_177/2013 du 6 juin 2013 consid. 3.3; 2C_587/2008 du 4 décembre 2008 consid. 4.1). L'autorité se fonde en principe sur un faisceau d'indices autonomes, aucun des critères n'étant souvent à lui seul déterminant pour juger du caractère fictif du mariage (cf. arrêts 2C_566/2013 du 2 décembre 2013 consid. 3.3; 2C_441/2007 du 9 janvier 2007 consid. 4.1). 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 (cf. art. 90 LEtr). 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êts 2C_177/2013 du 6 juin 2013 consid. 3.4; 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 (cf. arrêts 2C_177/2013 du 6 juin 2013 consid. 3.4; 2C_222/2008 du 31 octobre 2008 consid. 3.2; critiquant cette exigence: SYLVAIN FÉLIX, Présomptions et relations familiales en droit des étrangers, in Actualités du droit des étrangers [Corbaz/Amor/Nguyen (éd.)], vol. II, 2014, p. 1 ss, 9). En l'absence d'indices concrets suffisants, le mariage ne saurait cependant être qualifié de fictif. En cas de doute, il faut considérer que les époux voulaient fonder une véritable communauté conjugale (arrêts 2C_587/2008 du 4 décembre 2008 consid. 4.1; 2C_473/2008 du 17 novembre 2008 consid. 2.1, in Pra 2009 n° 63 p. 413).
5.3. En l'espèce, les éléments de fait, que le Tribunal cantonal a établis et appréciés sans verser dans l'arbitraire (consid. 4 supra) et sur la base desquels il a considéré que le mariage des recourants était uniquement destiné à procurer une autorisation de séjour à l'intéressé, se laissent résumer de la manière suivante: l'ignorance de certains détails importants sur l'autre époux, notamment sur la façon d'écrire les nom et prénom du conjoint; les déclarations divergentes des époux quant aux cadeaux de mariage échangés, à la durée du séjour de l'intéressée au Sénégal en vue du mariage, au mariage religieux célébré en l'absence des époux, et aux convives peu nombreux ayant participé à la réception tenue après le mariage à Dakar; l'absence de photographies (suffisamment) probantes relatives au mariage et à la rencontre des intéressés en Espagne. En sus de ces éléments qui, à eux seuls, ne sont certes pas susceptibles de retenir un mariage fictif, les juges cantonaux ont encore considéré que les époux n'avaient pas établi qu'ils entretenaient des contacts réguliers par téléphone ou d'autres moyens informatiques, les copies de SMS et les cartes produites n'attestant de tels échanges que durant un laps de temps limité. S'y ajoute la circonstance que la mère du recourant, vivant pourtant à Dakar, n'avait pas assisté au mariage de son fils, et qu'aucun membre de la famille de la recourante n'avait été présent. Les juges cantonaux ont également relevé que le recourant avait travaillé clandestinement plusieurs années en Europe, que son épouse lui avait envoyé de l'argent pour subvenir à ses besoins au Sénégal, pays où il était actuellement sans travail et qu'il souhaitait quitter pour avoir de meilleures conditions de vie en Suisse. Le projet de mariage était de plus survenu relativement tôt, soit en octobre 2013, alors que les époux s'étaient rencontrés en janvier 2012 et qu'ils ne s'étaient plus revus pendant près de deux ans; sur trois ans, les époux ont physiquement été ensemble moins d'un mois; si, comme les époux l'affirmaient, leur séparation les faisait autant souffrir, l'on ne comprenait pas pour quelle raison la recourante avait préféré rendre visite à sa famille en Italie durant ses vacances de juillet 2014, plutôt que de rejoindre son mari.
Contrairement à ce que prétendent les recourants, les nombreux éléments retenus par le Tribunal cantonal sont pertinents au regard des conditions que la jurisprudence précitée a admises pour pouvoir présumer de l'inexistence d'une relation conjugale réellement vécue et voulue entre les époux. Premièrement, certains de ces indices établissent une certaine méconnaissance réciproque des époux au sujet de leur propre mariage. Deuxièmement, les préparatifs du mariage des époux pouvaient être qualifiés de hâtifs au vu du peu de jours que les intéressés disent avoir passés ensemble avant de se rendre au Sénégal; l'absence de la mère du recourant et des membres de la famille de la recourante durant le mariage à Dakar corrobore également un mariage fictif. Troisièmement, la situation clandestine du recourant en Espagne et ses finances précaires, de même que son souhait, en soi compréhensible, d'améliorer ses conditions de vie en Suisse, constituent autant d'indices forts plaidant pour un mariage de complaisance. Quatrièmement, et tel que les recourants le concèdent eux-mêmes, ceux-ci n'ont jamais vécu ensemble avant leur mariage, pas plus qu'ils ont maintenu des contacts physiques après la célébration de celui-ci, même lorsque l'épouse aurait pu rejoindre son époux durant ses vacances.
5.4. Au vu de ce qui précède, il existe partant un faisceau d'indices suffisants et sérieux qui permet de présumer de l'absence d'une union conjugale réellement voulue et effective. A défaut de contre-preuves convaincantes de la part des recourants, qui se sont contenté de rediscuter les faits constatés (consid. 4 supra), leur mariage est donc réputé avoir été contracté dans le but d'éluder les dispositions en vigueur en matière de séjour et d'établissement des étrangers. Il s'ensuit qu'en déniant au recourant l'autorisation de séjourner en Suisse, l'arrêt querellé n'a violé ni le droit fédéral, ni les art. 13 Cst. et 8 CEDH. Les considérants qui précèdent conduisent ainsi au rejet du recours.
6.
Succombant, les recourants doivent supporter les frais judiciaires, solidairement entre eux (art. 65 et 66 al. 1 et 5 LTF). Il ne sera pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3.
Le présent arrêt est communiqué au mandataire des recourants, au Service de la population et des migrations, au Conseil d'Etat et au Tribunal cantonal du canton du Valais, Cour de droit public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 1er septembre 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Chatton