Faits : A. A.a. A._, domicilié à U._, est le titulaire de la raison individuelle C._, dont le siège est à V._. A.b. Le 12 décembre 2014, l'Office des poursuites de la Gruyère a notifié à A._, à l'instance de B._ SA, le commandement de payer n° xxxx, portant sur des montants de xxxx fr. plus intérêt et de xxx fr. Le 26 janvier 2015, cet office a notifié au débiteur la commination de faillite établie le 23 janvier 2015 dans la poursuite précitée. A.c. Après avoir entendu le poursuivi à son audience du 2 novembre 2015, personne ne s'étant présenté au nom de la créancière, la Présidente du Tribunal civil de la Gruyère (ci-après: la Présidente) a prononcé la faillite de A._ par décision du même jour. B. B.a. Son attention ayant été attirée par l'Office cantonal des faillites sur le fait que le failli était domicilié dans le district de la Sarine, la Présidente s'est adressée, par courrier du 20 novembre 2015, à la Chambre des poursuites et faillites du Tribunal cantonal de l'Etat de Fribourg (ci-après: la Chambre des poursuites et faillites), en tant qu'autorité de surveillance des offices des poursuites et des faillites, afin que soit examinée l'éventuelle nullité de la commination de faillite. B.b. Invités à se déterminer, A._ a indiqué le 2 décembre 2015, attestation du contrôle des habitants à l'appui, qu'il est effectivement domicilié à U._, tandis que B._ SA ne s'est pas manifestée. B.c. Par arrêt du 23 décembre 2015, la Chambre des poursuites et faillites a constaté que la commination de faillite n° xxxx, établie le 23 janvier 2015 par l'Office des poursuites de la Gruyère à l'encontre de A._, est nulle, mais a en revanche refusé de constater la nullité de la décision de faillite de A._ prononcée le 2 novembre 2015 par la Présidente du Tribunal civil de la Gruyère. C. Par acte posté le 8 janvier 2016, A._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt du 23 décembre 2015. Il conclut à son annulation et à sa réforme en ce sens que la nullité de la décision de faillite du 2 novembre 2015 est constatée. Il invoque une violation des art. 22, 46 al. 1, 166, 172 ch. 1 et 173 ch. 2 LP, ainsi que de l'art. 8 Cst. Invité à se déterminer, l'Office cantonal des faillites a indiqué se rallier à l'avis du recourant et a conclu à ce que le commandement de payer, la commination de faillite et la décision de faillite soient déclarés nuls au sens de l'art. 22 LP et à ce qu'ordre lui soit donné de lever, respectivement d'annuler, toutes les mesures prises dans l'intervalle. A l'appui de ses observations, l'office a notamment contesté l'allégation du recourant selon laquelle il n'avait pas commencé à exécuter le jugement de faillite. Conformément à l'art. 221 LP, il avait en effet procédé rapidement à l'interrogatoire du failli, à l'inventaire de ses actifs et au blocage de ses comptes bancaires. En revanche, suite à l'ordonnance du Tribunal fédéral du 16 janvier 2016, son matériel d'exploitation a été laissé à sa disposition et le bail n'a pas été résilié. L'intimée ne s'est pas déterminée dans le délai imparti à cet effet et l'autorité cantonale a indiqué renoncer à déposer une réponse. D. Par ordonnance présidentielle du 28 janvier 2016, l'effet suspensif a été attribué au recours en ce sens que le prononcé de la faillite reste en force mais qu'aucun acte d'exécution de la décision attaquée ne doit être entrepris, les éventuelles mesures conservatoires déjà prises par l'Office des faillites (art. 162 ss, 170, 174 al. 3 et 221 ss LP) demeurant toutefois en vigueur.