There are many stories that are told over about the people who lived in Chelm. They all have the theme of: the people in Chelm were fairly unintelligent. Where did this come from? Is it true? It sounds highly unlikely that a whole city would be more unintelligent then the next city.
I've always speculated that it came from the fact that at one time Chelm had a very wise rabbi, named R' Shlomo (d. 1717). He is famous for his book Mirkeves Hamishneh, a commentary on the Rambam's Yad Hachazakah; appended to it is a work called Kuntreis Breichos Becheshbon, which analyzes difficult mathematical problems in the Torah. (Parts of the latter have been adapted into English under the title "Approaching Infinity," by M. Littman.)
So conceivably, by comparison to R' Shlomo, everyone else in Chelm seemed like a fool!
According to my Lithuanian grandparents, Chelm was a joke name used to make fun of Kelm.
The city of Chelm is located in Poland, while the city of Kelm (Kelmé) is located in Lithuania. I don't recall if a reason was given for the switching of names, whether it has to do with mocking Polish in general or whether it was simply a matter of mispronouncing the name so as to aggravate and mock the Kelmites.
Kelm was home to one of the outstanding Yeshivas in its time, the Yeshiva of Kelm, or Talmud Torah of Kelm.
This mockery was originally started by Maskilim trying to ridicule the Bnei Torah who learned there.
Looking here you will see how many famous Rabbis actually learned there.
However people who don't know better and would never mock Bnei Torah seemed to have picked up on this joke and continued it without realizing how it started.
(Perhaps the strong association of this Yeshiva with the Mussar helped this trend, but that is my own speculation.)