Flea market comes from the French march� aux puces, a name originally given to a market in Paris. The fleas were thought to be in the goods, because they were of the kind to attract vermin. The earliest English use found dates from 1922
Alternately, here in the U.S. the odd phrase is attributed to the Dutch...when there was a very real Vallie (Valley) Market at the valley, or foot, of Maiden Lane in Downtown Manhattan. The Vallie Market came to be abbreviated to 'Vlie Market' and this was soon being pronounced 'Flea Market.'" From Encyclopedia of Word and Phrase Origins by Robert Hendrickson (Facts on File, New York, 1997). One takes one's pick...