Martin Wainwright tells the following story in The "Guardian" Book of April Fool's Day
[The journalist James] Bone described on one occasion how a desperate contributor of 'pars', small fillers for the popular press, went to send a letter from a post office and noticed that the pet cat on the counter was sitting with its tongue out. On a whim, he gave it his stamp to lick which it did. The next day a very short story appeared under the headline: Post Office novelty — Stamp-licking cat of Charing Cross'.
Like the best April Fool's jokes, this was to girdle the Earth. Not only was the post office besieged by punters wanting to send catlick mail (until the cat was driven demented and fled after two days) but the story spread and resurfaced for years. Animal protection societies weighed in, MPs spoke and the innocuous prank took off. Bone's friend was send clippings from across the country and, as the years went by, from Australia, Shanghai and the United States.
This suggests that stamp-licking animals were a journalistic invention. However, there do seem to have been some real-life examples of the phenomenon.
Longview Daily News - Dec 13, 1974
The Bloomington Pantagraph - Mar 11, 1951
"Ashley practiced stamp-licking until he had the task down purrfectly, then offered to kick off the Organization for Responsible Care of Animals' public appeal... In return for his generosity, each donor will receive a thank-you note enclosed in an Ashley-licked envelope with stamp attached."
Lancaster Sunday News - Oct 6, 1985