This paper studies approximations for a class of nonlinear filters known as Volterra filters. Although the Volterra filter provides a relatively simple and general representation for nonlinear filtering, often it is highly over-parameterized. Due to the large number of parameters, the utility of the Volterra filter is limited. The over-parameterization problem is addressed in this paper using a tensor product basis approximation (TPBA). In many cases a Volterra filter may be well approximated using the TPBA with far fewer parameters. Hence, the TPBA offers considerable advantages over the original Volterra filter in terms of both implementation and estimation complexity. Furthermore, the TPBA provides useful insight into the filter response. This paper studies the crucial issue of choosing the approximation basis. Several methods for designing an appropriate approximation basis and error bounds on the resulting mean-square output approximation error are derived. Certain methods are shown to be nearly optimal.