We present practical approaches for steganography that can provide improved security by closely matching the second-order statistics of the host rather than just the marginal distribution. The methods are based on the framework of statistical restoration, wherein a fraction of the host symbols available for hiding is actually used to restore the statistics; thus reducing the rate, but providing security against steganalysis. We establish correspondence between steganography and the earth-mover's distance (EMD), a popular distance metric used in computer vision applications. The EMD framework can be used to define the optimum flow (modifications) of the host symbols for compensation. This formulation is used for image steganography by restoring the second-order statistics of the blockwise discrete cosine transform (DCT) coefficients. Some practical limitations of this approach (such as computational complexity and difficulty in dealing with overlapping coefficient pairs) are noted, and a new method is proposed that alleviates these deficiencies by identifying the coefficients to modify based on a local compensation criterion. Experimental results on several thousand natural images demonstrate the utility of the presented methods.