Let me take a completely different approach, to add to Johannes' answer.
FPS or "frames per second" originates in the film world.
35mm film used to run run at 24 frames per second. In other words, the motion you saw on screen as continuous was actually due to "persistence of vision" creating a fluid motion out of 24 discrete images or Frames. With video came other frame rates. Countries with 110volts electricity at 60 Hz chose 30 fps as it was easy to keep perfect time this way. Other countries with 50Hz chose 25 frames per second (see the relation?).
Digital video and encoding came into the picture, we started talking in terms of bitrates or the amount of information contained (in a frame or per second). With the same kind of encoding algorithm, higher bitrates usually offer better quality. But the same amount of data in a smaller frame (=fewer pixels) also means better quality. And obviously if measured in seconds, you add more data if there are more frames per second.
Conversely, if you are using say 1024 KBps (kilobytes per second), then for 60 fps it gives lower quality than at 24 fps, because there's fewer frames in 24fps over which this 1024 is distributed, that is 1024/24 = 42.6 KB per frame. With 60 fps, it is only 17.06 kilobytes per frame.
Although this is simplistic in many ways, it does give a general idea.