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.