There’s a most entertaining article in Chambers 1869 Book of Days on April 1st. (Scroll down to April Fools.) After some amusing examples of popular gags and a couple of paragraphs on the distinction between Scottish and English fooling the article goes on to discuss the origins, which it admits are obscure.
The literature of the last century, from the Spectator downwards, has many allusions to April fooling; no references to it in our earlier literature have as yet been pointed out. English antiquaries appear unable to trace the origin of the custom, or to say how long it has existed among us. In the Catholic Church, there was the Feast of the Ass on Twelfth Day, and various mummings about Christmas; but April fooling stands apart from these dates.
April fooling is a very noted practice in France, and we get traces of its prevalence there at an earlier period than is the case in England. For instance, it is related that Francis, Duke of Lorraine, and his wife, being in captivity at Nantes, effected their escape in consequence of the attempt being made on the 1st of April. ‘Disguised as peasants, the one bearing a hod on his shoulder, the other carrying a basket of rubbish at her back, they both at an early hour of the day passed through the gates of the city. A woman, having a knowledge of their persons, ran to the guard to give notice to the sentry. “April fool!” cried the soldier; and all the guard, to a man, shouted out, “April fool!” beginning with the sergeant in charge of the post. The governor, to whom the story was told as a jest, conceived some suspicion, and ordered the fact to be proved; but it was too late, for in the meantime the duke and his wife were well on their way. The 1st of April saved them.’
It certainly appears, as Dave notes, that the practice came to England from across the Channel.