Synchrotron radiation from active galactic nuclei (AGN) is often highly polarized. We present a search for linear polarization with the Very Large Array (VLA) at 4.8 GHz and 8.4 GHz from the nearest AGN, Sagittarius A*. As a part of this study we used spectro-polarimetric data that were sensitive to a rotation measure (RM) as large as 3.5* 106\rdm at 4.8 GHz and 1.5* 107\rdm at 8.4 GHz. The upper limit to the linear polarization of Sgr A* over a broad range of RM is 0.2% at both frequencies. We also present continuum observations with the VLA at 4.8 GHz which give an upper limit of 0.1% for RMs less than 104 \rdm. We conclude that depolarization is unlikely to occur in the Galacter Center scattering medium. However, it is possible for depolarization to occur in the accretion region of Sgr A* if the outer scale of turbulence is small enough. We also consider the implications of a very low intrinsic polarization for Sgr A*.