This cat said:
"It's a poor sort of memory which only works backward."

Some dark night when you are outside, looking through a tree's branches at either a first quarter or last quarter moon which is illuminated on the lower portion of the moon, you will see what Lewis Carroll saw one night which gave him the idea of the Cheshire Cat.

It's even better if there are a couple of bright stars where the cat's eyes might be.

The term had been reused repletely
And in fact abused completely
By the time he wrote the tale
Of this girl's miraculous fall

Where it came from no one knows
But it had been claimed by those
Who sell cheeses made in Cheshire
That it comes from cheese's mold

And by people hanging signs
Amongst the Cheshire country pines
That said a grinning lion symbol
Had been there from days untold

But seriously, the idea of a grinning Cheshire cat wasn't Carroll's - it's certainly documented as early as 1808 and may have gone a while back. Cheshire cheese was sold molded in a grinning cat shape, and it was even suggested that the cat disappearing from tail to smile was equivalent to slicing the cheese from one side to the other. It's also noted that many signs on Cheshire inns sported drawings of smiling lions. Carroll, who was born in Cheshire, would have been familiar with this image.