Yes, lossless compression takes advantage of the fact that many files are not random. Yes, most multimedia files are not random.
Fax images are a good example of this effect. In their simplest form, a fax image is a 2-D black-and-white image, obtained by scanning a single page of some document. If you represent this image as a sequence of bits, one bit per pixel (0 = white, 1 = black), then you will discover that the resulting binary data is not at all random. For instance, here are some non-random patterns you will spot:
Typically fax images have a lot more white pixels than black pixels.
Also, each pixel is more likely to have the same color as the pixel to its left than to have a different color.
For a more sophisticated pattern: Imagine scanning pixels horizontally, left to right, and counting the length of each "run" of consecutive pixels with the same color. Then long runs are more common than short runs, and long runs of white pixels are more common than long runs of black pixels.
Fax compression algorithms were designed to take advantage of these non-random aspects. Early fax compression algorithms are a particularly good example, because they are simple lossless compression schemes that very directly exploit these non-random properties of scanned images.
For instance, one early scheme for compressing fax images used run-length encoding combined with Huffman encoding. Run-length encoding replaces each run of same-color pixels with a single integer counting the length of the run. For instance, 00000110001 becomes "5 2 3 1". Run-length encoding exploits the fact that pixels tend to come in runs of the same color. The Huffman encoding further exploits the fact that some run-lengths are more common than others. See here for a detailed example of how one of these early schemes worked -- the scheme is simple and elegant, and directly exploits the patterns mentioned above.
These schemes would not offer any compression, on average, for random files. However, scanned fax images are not random, and as a result these compression schemes can offer substantial savings.
Similar comments apply to other multimedia files. The patterns present in other kinds of multimedia files can be more complex, but there are still many patterns present that make the data non-random.