1) cluster all possible 8x8 pixel video blocks by some metric, and pick the 256 most frequent ones.

2) include these into a new charset, or several character sets up to how much memory you want to use, with the most frequent 8x8 pattern occuring.

3) Now encode each frame by 'quantizing' an 8x8 block into its character code. You want to minimize overall perceptual error, so choosing the optimal charset tile patterns and optimal tiling can be done with many optimization techniques (monto carlo, genetic algorithms, etc)

But basically, you're 'dithering' the frame down to characters in a font, and the font character patterns must be chosen optimally to fit the whole video. There's some leeway in this because you can change the font every scanline or 8 scanlines, so it is possible to go beyond a max of 256 unique tiles per frame, you could also switch fonts between different parts of the video.

A given full screen would be 40x25 characters, so you'd need to decode/write about 1000 characters per frame. At 10fps, you need to decode about 10k per second. The c64 executes about 20k cycles per frame, and the time to load/store from memory is going to be at least 9 cycles, 13 if you use indirect addressing. That gives you enough time to barely write 1500 bytes per frame, so this is right at the limit of what the C64 can do. You decompression has to be essentially a table lookup, and minimally a loop if I've estimated the bounds correct. (I'm going by 20 year old memory :) )