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 x 10^6 rad m^-2 at 4.8 GHz and 1.5 x 10^7 rad m^-2 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 10^4 rad m^-2. 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*.