GIF has two major compression methods: 1) RLEncoding and 2) the Palette Lookup color table.
JPEG has two as well: 1) Discrete Cosine Transform or Wavelet Transform and 2) Reduction of Hue and Saturation in favor of Luminance
JPEG uses the discrete cosine transform and JPEG2000 uses the wavelet transform. For both techniques, degradation (or loss) comes from the quantizer stage, which follows the transform stage. It is in this stage that data is "thrown out" so that the result an be compressed.
[Photoshop uses] the Nigel Tufnel-trick to force the program mode to switch over to a truly loseless version of the JPEG algorithm.
- Ken Prager