Faits : A. Par ordonnance pénale du 19 janvier 2015, X._ a été condamné pour entrave à l'action pénale, à une peine privative de liberté de six mois, sans sursis, sous déduction de deux jours de détention. B. A la suite de l'opposition formée par X._ contre l'ordonnance pénale précitée, le Juge de police de la Veveyse a, par jugement du 29 mai 2015, confirmé sa condamnation pour entrave à l'action pénale ainsi que la peine infligée. C. Statuant le 15 décembre 2015 sur l'appel de X._, la Cour d'appel pénal du Tribunal cantonal de l'Etat de Fribourg l'a partiellement admis en ce sens qu'elle l'a condamné à une peine pécuniaire ferme de 90 jours-amende, le montant du jour-amende étant fixé à 40 fr., sous déduction de deux jours-amende correspondant à la détention avant jugement subie. En bref, il en ressort les faits suivants. Le 25 juillet 2013, vers 19h35, A._ et son codétenu, B._, se sont évadés de la prison C._, aidés par deux comparses qui ont fait usage d'armes de guerre, afin de tenir en respect les agents pénitentiaires et de sécurité. A._ a été arrêté le 28 août 2013 par la police cantonale vaudoise alors qu'il était passager d'un véhicule conduit par X._. Rapidement, ce dernier a admis avoir hébergé le fugitif et certains de ses comparses à partir des 12, 13, respectivement 18 août 2013. La police a également procédé à des contrôles téléphoniques rétroactifs qui ont permis d'établir l'existence de communications téléphoniques entre X._, un certain D._ et A._ durant la période du 14 juin au 17 juillet 2013. D. Le 23 septembre 2013, la réintégration de X._, qui se trouvait en libération conditionnelle d'une peine à vie prononcée en 1984, a été ordonnée. Sa libération a été révoquée (cf. arrêt 6B_720/2014 du 17 novembre 2014). E. Le Ministère public de l'Etat de Fribourg forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 15 décembre 2015, concluant principalement à sa réforme en ce sens que la peine privative de liberté de six mois, sans sursis, sous déduction de deux jours de détention avant jugement, prononcée par jugement du 29 mai 2015 est confirmée. Subsidiairement, il requiert son annulation et le renvoi de la cause à l'autorité précédente pour nouvelle décision. Invités à se déterminer sur le recours, la cour cantonale y a renoncé, alors que X._ a conclu au rejet. Il sollicite en outre l'assistance judiciaire, comprenant la désignation de son conseil en qualité d'avocat d'office.