No one disputes that the expression "chew the fat" now means to have a chat or discuss something, usually in an unhurried manner over a fairly long period of time. However, the origin of the expression is not at all clear.

Despite a "Life in the 1500s" document circulating around the Internet which claims the phrase dates to that period (and apparently the tours of William Shakespeare's wife Anne Hathaway's cottage give this same supposed factoid), it is not nearly that old. Its first recorded use is in the second half of the 1800s, and it may have originated during the American Civil War. (It may be related to "chew the rag," a phrase first recorded around 1885, where the rag is either a chewing tobacco substitute or slang for the tongue.)

Most theories feel that it comes from the common use of salt pork as a food in 1800s America; chewing the fat from this took a lot of effort for not much reward, somewhat like the talk and gossip associated with "chewing the fat" in the metaphorical sense. Salt pork was common in both army rations and the food stored for sailing ship voyages, so some attribute this phrase to military or sailor slang -- people complaining about the food while they ate it. Though the majority of theories attribute the phrase to the U.S., the American Heritage Dictionary of Idioms says that up until the 1880s the phrase meant "to grumble or complain," in Britain, so it must have been around there at the time as well as across the Atlantic. This older meaning does help refute the claim of one web site that it is Cockney Rhyming Slang for "have a chat." Another site makes the claim that it comes from the Inuit practice of chewing on blubber like chewing gum, but there is no reputable support for that origin theory.

Sources:
http://wordsmith.org/awad/archives/0402
http://www.xrefer.com/entry.jsp?xrefid=630269&secid=.-
http://www.funtrivia.com/Miscellaneous/Origins.html
http://pw1.netcom.com/~rlederer/arcwdcr2.htm
http://www.takeourword.com/TOW112/page2.html
http://www3.teleplex.net/timonier/speaks/book01.html
http://www.cockney.co.uk/04a1.htm
http://members.aol.com/MorelandC/HaveOriginsData.htm#ChewTheFat