Calculating optimal policies is known to be computationally difficult for Markov decision processes with Borel state and action spaces and for partially observed Markov decision processes even with finite state and action spaces. This paper studies finite-state approximations of discrete time Markov decision processes with discounted and average costs and Borel state and action spaces. The stationary policies thus obtained are shown to approximate the optimal stationary policy with arbitrary precision under mild technical conditions. Under further assumptions, we obtain explicit rates of convergence bounds quantifying how the approximation improves as the size of the approximating finite state space increases. Using information theoretic arguments, the order optimality of the obtained rates of convergence is established for a large class of problems.