Short answer:
Blocks are units for inter-frame comparison;
Prediction is based on amount of blocks presenting on both previous and following images;

Longer answer:
As input, a video encoder receives nothing else but a sequence of frames.
In most cases, the adjacent frames are very similar to each other, and the encoder attempts to figure out whether these frames are indeed similar.

How do you say if two images are similar?

• Both images are split into macroblocks (you can’t compare entire images, they will certainly differ!)
• The algorithm attempts to find if a block from previous image exists on the following image (within a certain proximity to its original position)
• If, to a certain threshold, most of the blocks present on the following image, the following image is computed as a difference to the previous one (P-frame);
  • Of course, differing blocks are encoded as-is;
• If not, the following image is considered to belong to another scene, and there’s no other way rather than keeping it entirely (I-frame).

In order to understand how prediction works, take a look at this image. It is created by a deshaker plug-in for VirtualDub, and used for a different purpose (detecting camera shakes), but it seems very representative:

The arrows indicate how the current image differs to the previous one;
The entire frame is split into macroblocks (larger than 16×16, however);
The difference for each block, compared to the previous image, is a movement vector;
As you see, most macroblocks (white arrows) follow the common pattern, and therefore they can be encoded by only applying a transposition matrix to a previous frame.
However, there are some blocks (red arrows) do not comply with the common pattern, and therefore they must be encoded as-is.
Of course, if everything is red, there’s no choice other than encoding the entire frame as-is.