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)