Sgr A* is variable at radio and submillimeter wavelengths on hourly time scales showing time delays between the peaks of flare emission as well as linearly polarized emission at millimeter and sub-mm wavelengths. To determine the polarization characteristics of this variable source at radio frequencies, we present VLA observations of Sgr A* and report the detection of polarized emission at a level of 0.77+/-0.01% and 0.2+/-0.01% at 43 and 22 GHz, respectively. The change in the time averaged polarization angle between 22 and 43 GHz corresponds to a RM of -2.5+/-0.6 *103 rad m-2 with no phase wrapping (or 5*104 rad m2 with 2\pi phase wrap). We also note a rise and fall time scale of 1.5 - 2 hours in the total polarized intensity. The light curves of the degree of linearly polarized emission suggests a a correlation with the variability of the total intensity at 43 GHz. The available polarization data at radio and sub-mm wavelengths suggest that the rotation measure decreases with decreasing frequency. This frequency dependence, and observed changes in polarization angle during flare events, may be caused by the reduction in rotation measure associated with the expansion of synchrotron-emitting blobs.