Apparently Donald Mackay defined information as the distinction that makes a difference, which is similar to, though less memorable than, Bateson's "The difference that makes a difference".
I can't find it in Mackay's main work on information - "Information, Mechanism and Meaning" (MIT Press 1969) - or any other publications of Mackay's that I've seen so far, though I can believe it accords with his understanding of information.
If anyone knows the origin of the phrase, please let me know.
Update: after private communication with a couple of the authors who had 'quoted' this expression and referenced Mackay, no one has been able to identify the source. It would appear to be a myth!