Techniques for estimating the stationary distribution of deterministic systems based on a discrete Markov approximation of the dynamics are well known and have been successfully used in the past. We now extend these techniques to random dynamical systems by defining a suitably averaged Markov model. We find that these constructions are often superior to iterative orbit based methods and for some classes of maps provide rigorous error bounds for our estimates of the stationary distribution.