It doesn't have to be random, it has to be complete. Random is definitly better, but it's unlikely that steganography would be needed if one could send random data for any reason to begin with. You want the message to be invisible, and anyone looking for hidden messages is certain to scan "random" data and check it for statistics. The power of statistics makes steganography really hard.
The key is to steganographically encode "random" (encrypted) data and then "shape" the result to match the mean probabilities seen in observation of a system in usual operation. This defeats statistical analysis, since your data is shaped just like everyone else's. If the bits are encrypted with a recipient's public key, only with posession of the private key can the data be perceived to be non-random, which is a nicely strong property. -David Weekly