Sgr A* is variable at radio and submillimeter wavelengths on hourly timescales, showing time delays between the peaks of flare emission as well as linearly polarized emission at millimeter and submillimeter 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 2p phase wrap). We also note a rise and fall timescale of 1.5-2 hr in the total polarized intensity. The light curves of the degree of linearly polarized emission suggest a correlation with the variability of the total intensity at 43 GHz. The available polarization data at radio and submillimeter 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.