I've observed that when you view only the LSB of an image it is typically random looking, but often has areas that correlate with the over all structure of the image. It's common for there to be large sections of the image that are solid 1s or 0s. There are often blocky patterns. Complete randomness of the LSB would therefor be a potential indicator that steganography is present.
I am considering a simple block based technique. Consider a grayscale image. Divide the image into 2x2 pixel blocks, LSB only. There are 16 possible permutations, which are grouped into sets of twos. Blocks that match the first set (four white pixels, or four black pixels) are ignored. Blocks that match the other seven sets will encode our ciphertext. One of two possible patterns is chosen based on the bit of the ciphertext we are storing. Optionally, we may look at neighboring blocks (up, down, left, right) and if they are of the four solid pixel variety then we also ignore this block. For color images you could do this separately for each color channel.
This would essentially only store bits of ciphertext in parts of the image that appear random. Every block that stores a bit of ciphertext is only ever replaced with a block that is a flipped version of itself, so the number of 1s and 0s always remains the same.
Can someone more mathematically inclined and familiar with steganography weigh in on how effective this approach might be?