The story of the cat and elephant's "Strange Companionship" is from Innocents Abroad, Chapter 11.

The boon companion of the colossal elephant was a common cat! This cat had a fashion of climbing up the elephant’s hind legs and roosting on his back. She would sit up there, with her paws curved under her breast, and sleep in the sun half the afternoon. It used to annoy the elephant at first, and he would reach up and take her down, but she would go aft and climb up again. She persisted until she finally conquered the elephant’s prejudices, and now they are inseparable friends. The cat plays about her comrade’s forefeet or his trunk often, until dogs approach, and then she goes aloft out of danger. The elephant has annihilated several dogs lately that pressed his companion too closely.