The Cheshire cat is now largely identified with the character in Alice’s Adventures in Wonderland (1865), by the English writer Lewis Carroll (Charles Lutwidge Dodgson – 1832-98):

“Please would you tell me,” said Alice, a little timidly, for she was not quite sure whether it was good manners for her to speak first, “why your cat grins like that?”
“It’s a Cheshire cat,” said the Duchess, “and that’s why.”

But the phrase was already well established. For example, in the second edition of A Classical Dictionary of the Vulgar Tongue (1788), Francis Grose wrote:

Cheshire Cat. He grins like a Cheshire cat; said of any one who shews his teeth and gums in laughing.

The origin of this expression is unknown. There are two leading theories. The first one was apparently first proposed by a contributor to Notes and Queries of 16^th November 1850, signing himself T. D., who wrote the following from Bath:

Some years since Cheshire cheeses were sold in this town moulded into the shape of a cat, bristles being inserted to represent the whiskers. This may possibly have originated the saying.

But no evidence that such cheeses were produced has been found.

The second theory seems to have first appeared in Notes and Queries of 24^th April 1852. A contributor, signing himself H, wrote:

I remember to have heard many years ago, that it [= the phrase “to grin like a Cheshire cat”] owes its origin to the unhappy attempts of a sign painter of that county to represent a lion rampant, which was the crest of an influential family, on the sign-boards of many of the inns. The resemblance of these ‘lions’ to ‘cats’ caused them to be generally called by the more ignoble name. A similar case is to be found in the village of Charlton, between Pewsey and Devizes, Wiltshire. A public-house by the roadside is commonly known by the name of ‘The Cat at Charlton.’ The sign of the house was originally a lion or tiger, or some such animal, the crest of the family of, I believe, Sir Edward Poore.

But one can doubt the theory of somebody who “remember[s] to have heard many years ago” of these “unhappy attempts”. (Lewis Carroll, who was born in Cheshire, was a subscriber to Notes and Queries from its inception until his death and may well have grinned at these linguistic speculations.) Additionally, in Our Old Country Towns (1881), the artist and author Alfred Rimmer (1829-93) wrote:

Against this derivation, which Mr. Legh [sic] is by no means satisfied with, must be put the circumstance that other counties than Cheshire are equally well supplied with lions for family devices, and these are quite as liberally distributed over the inn doors.

Alfred Rimmer refers to A Glossary of words used in the dialect of Cheshire, published in 1877, by Egerton Leigh (1815-76). Before quoting the latter, I transcribe the explanation proposed by the former:

The extinct, or nearly extinct, wild animals, such as the badger and wild-cat, lingered here longer than in other parts, and some years since a veritable specimen of the latter was shot on Peckforton Moss by a friend of the writer’s. It was much heavier than any domestic cat, and some naturalists say that the wild-cat was of a different species. The face and mouth were very wide, and so ferocious did they look when disturbed, that it was easy to see why to “grin like a Cheshire cat” is yet a common proverb in the north of England.

But the most likely explanation was given by Egerton Leigh in the above-mentioned glossary:

“To grin like a Cheshire cat” is a very old saying, and like many old sayings, the origin is doubtful. Another version is “to grin like a Cheshire cat chewing gravel.” […] Still another amplified version is “to grin like a Cheshire cat eating cheese.” This may be supposed to produce a smile of satisfaction rather than a grin of disgust. […]
One need not go far to account for a Cheshire cat grinning. A cat’s paradise must naturally be placed in a county like Cheshire, flowing with milk.

In A Dictionary of Slang and Unconventional English (8^th edition – 1984), by Eric Partridge, edited by Paul Beale, it is surmised that a Cheshire Cat is an alteration of a cheeser cat, from a cheeser, that is, a cat very fond of cheese. To grin like a Cheshire cat would therefore be to be as pleased as a ‘cheeser’ that has just eaten cheese. It is alternatively conjectured in the same dictionary that the development could have been from cheeser to Cheshire cat via Cheshire-cheeser.