There is, unfortunately, no certainty about the origin of this word.
But Isaac D’Israeli (the father of the statesman, Benjamin Disraeli), in Curiosities of Literature, published in 1791, quoted a story that went the rounds of the British navy in 1700 which was then thought to explain the source.
The quoted explanation ran: “There was, sir, in our time one Captain Fudge, commander of a merchantman, who upon his return from a voyage, how ill-fraught soever his ship was, always brought home his owners a good cargo of lies, so much that now aboard ship the sailors, when they hear a great lie told, cry out, ‘You fudge it.'”
The story may be true, for there was a real Captain Fudge living in the seventeenth century, and he was said to have been known by some as “Lying Fudge,” but the explanation is not generally accepted as the source of our word.