In this study, Bayesian image denoising, in which the prior distribution is assumed to be a Gaussian Markov random field (GMRF), is considered. Recently, an effective algorithm for Bayesian image denoising with a standard GMRF prior has been proposed, which can help implement the overall procedure and optimize its parameters in O(n)-time, where n is the size of the image. A new GMRF-type prior, referred to as a hierarchical GMRF (HGMRF) prior, is proposed, which is obtained by applying a hierarchical Bayesian approach to the standard GMRF prior; in addition, an effective denoising algorithm based on the HGMRF prior is proposed. The proposed HGMRF method can help implement the overall procedure and optimize its parameters in O(n)-time, as well as the previous GMRF method. The restoration quality of the proposed method is found to be significantly higher than that of the previous GMRF method as well as that of a non-local means filter in several cases. Furthermore, numerical evidence implies that the proposed HGMRF prior is more suitable for the image prior than the standard GMRF prior.