I've generally used RLE for compressing graphics on the Apple/6502; obviously there are better algorithms for getting the size of the compressed image much smaller than that, but it's simple to do and gives a fair amount of compression, so it's been good enough. Variations on the RLE theme were pretty common on the Apple II; for example, to create the effect of more colors, it was common to make even rows be one color and odd rows be a different color, so rather than compress the image in the order it was stored in memory, the odd rows would be compressed, then the even rows (or vice versa). The modern equivalent of this RLE-style compression would be a .png file. (.png files support many more features, of course.)
Another common compression method was to store a sequence of commands to redraw the picture, in assembly, it might look like:
Code:
POINT EQU 0
LINE EQU 1
LINETO EQU 2
RECT EQU 3
SQUARE EQU 4
CIRCLE EQU 5
FILL EQU 6
DB POINT,X1,Y1
DB LINE,X2,Y2,X3,Y3
DB LINETO,X4,Y4 ; same as LINE,X3,Y3,Y4,Y4
DB RECT,X5,Y5,X6,Y6
DB SQUARE,X7,Y7,LENGTH_OF_SIDE
DB CIRCLE,X8,Y8,RADIUS
DB FILL,Y9,X9 ; flood fill
This method was used in a number of adventure games; when you went from one room to the next, you'd watch it draw the scene, giving it a slightly animated feel; for example, if you went outside, it might draw house as a triangle on top of a square, and the then paint the house using the flood fill (well, there'd be doors and windows too, but you get the idea). For speed reasons, a simplified flood fill algorithm was typically used. This simplified algorithm wouldn't be able to fill complex shapes like spirals. Instead the simplified flood fill would be called multiple times at different starting coordinates to fill in a complex shape section by section. The modern equivalent of this compression method would be a .svg file (or a postscript file).
In terms of compression that wasn't graphics-specific, plain old Huffman compression was used, but was ultimately supplanted by a utility called Shrinkit, which supported multiple compression methods (the modern equivalent here being a .zip file). LZW/LZ78-style compression was the method commonly used. There's a C program out there whose name escapes me (Nulib, maybe?) written for maximum portability so that Shrinkit archive files can be created/extracted/viewed under DOS, Unix, etc.
Anyway, it depends on what you're hoping to accomplish. Whether you want decompression to be fast, so that pictures can be displayed quickly, or whether you want the compressed image to be as small as possible so that you can fit as many images in memory as possible, etc.