Spatial statistical analysis of massive amounts of spatial data can be challenging because computation of optimal procedures can break down. The Spatial Random Effects (SRE) model uses a fixed number of known but not necessarily orthogonal (multiresolutional) spatial basis functions, which gives a flexible family of nonstationary covariance functions, results in dimension reduction, and yields optimal spatial predictors whose computations are scalable. By modeling spatial data in a hierarchical manner with a process model that includes the SRE model, the choice is whether to estimate the SRE model's parameters or to take a Bayesian approach and put a prior distribution on them. In this article, we develop Bayesian inference for the SRE model when the spatial basis functions are multiresolutional. Then the covariance matrix of the random effects decomposes naturally in terms of Givens angles and eigenvalues, for which a new class of prior distributions is developed. This approach to prior specification of a spatial covariance matrix offers remarkable improvement over other types of priors used in the random-effects literature (e.g., Wishart priors), as demonstrated in a simulation experiment. Further, a large remote-sensing dataset of aerosol optical depth (AOD), from the Multi-angle Imaging SpectroRadiometer (MISR) instrument on the Terra satellite, is analyzed in a fully Bayesian framework, using the new prior, and compared to an empirical-Bayesian analysis. © 2011 American Statistical Association.