  We present a study of variable faint optical sources discovered by comparing
the Sloan Digital Sky Survey (SDSS) and the Palomar Observatory Sky Survey
(POSS) catalogs. We use SDSS measurements to photometrically recalibrate
several publicly available POSS catalogs; a piecewise recalibration in 100
arcmin2 patches generally results in an improvement of photometric accuracy
(rms) by nearly a factor of two, compared to the original data. The POSS I
magnitudes can be improved to ~0.15 mag accuracy, and POSS II magnitudes to
\~0.10 mag accuracy. We use the recalibrated catalogs for the ~2,000 deg2 of
sky in the SDSS Data Release 1 to construct a catalog of ~60,000 sources
variable on time scales 10-50 years. A series of statistical tests based on the
morphology of SDSS color-color diagrams, as well as visual comparison of images
and comparison with repeated SDSS observations, demonstrate the robustness of
the selection methods. We quantify the distribution of variable sources in the
SDSS color-color diagrams, and the variability characteristics of quasars. We
detect a turn-over in quasar structure function which suggests that the
characteristic time scale for quasar variability is of the order one year. The
long-term (>1 year) quasar variability decreases with luminosity and rest-frame
wavelength similarly to the short-term (<1 year) behavior. We also demonstrate
that candidate RR Lyrae stars trace the same halo structures, such as the Sgr
dwarf tidal stream, that were discovered using repeated SDSS observations. We
utilize the POSS-SDSS selected candidates to constrain the halo structure in
the parts of sky for which repeated SDSS observations do not exist. (abridged)
