Below is an extract from Wikipedia's article on the origins of April Fools day. An interesting side note is that Wikipedia is preventing editing of the story today, as they're afraid of the pranks folks might pull in accordance with the holiday. As always on this day, read everything with a healthy dose of skepticism.
... Though the 1st of April appears to have been anciently observed in Great Britain as a general festival, it was apparently not until the beginning of the 18th century that the making of April-fools was a common custom.
In Scotland the custom was known as "hunting the gowk," i.e. the cuckoo, and April-fools were "April-gowks," the cuckoo being there, as it is in many countries, a term of contempt.
In France the person fooled is known as poisson d'avril. This has been explained from the association of ideas arising from the fact that in April the sun quits the zodiacal sign of the fish. A far more natural explanation would seem to be that the April fish would be a young fish and therefore easily caught. The French traditionally celebrated this holiday by placing dead fish on the backs of friends. Today the fish has been replaced with paper cut-out. ...