The Stokes-Brinkman equations model fluid flow in highly heterogeneous porous media. In this paper, we consider the numerical solution of the Stokes-Brinkman equations with stochastic permeabilities, where the permeabilities in subdomains are assumed to be independent and uniformly distributed within a known interval. We employ a truncated anchored ANOVA decomposition alongside stochastic collocation to estimate the moments of the velocity and pressure solutions. Through an adaptive procedure selecting only the most important ANOVA directions, we reduce the number of collocation points needed for accurate estimation of the statistical moments. However, for even modest stochastic dimensions, the number of collocation points remains too large to perform high-fidelity solves at each point. We use reduced basis methods to alleviate the computational burden by approximating the expensive high-fidelity solves with inexpensive approximate solutions on a low-dimensional space. We furthermore develop and analyze rigorous a posteriori error estimates for the reduced basis approximation. We apply these methods to 2D problems considering both isotropic and anisotropic permeabilities.