A expressão original é doido de pedras ou louco de pedras, e os dicionários do século XIX explicam-na como “aquele que atira pedras”. O dicionário mais antigo em que encontrei a expressão é o de António Moraes da Silva de 1831, no verbete pedra:
PEDRA […] §. Doido de pedras, o que atira pedradas.
O Diccionario Encyclopedico de José Maria de Almeida e Araujo Corrêa de Lacerda (4ª edição, Lisboa, 1874) no verbete pedra elabora um pouco mais:
Doido de —s, que atira pedras desatinadamente: (fig.) homem estouvado.
Aparentemente, atirar pedras era uma coisa que os doidos faziam, pois Raphael Bluteau regista em 1713 o adágio «De doudo pedrada, ou má palavra» no seu Vocabulario Portuguez e Latino (verbete Doudo):

As ocorrências mais antigas que encontrei da expressão no Google Books (século XVII, enquanto que com pedra, no singular, só em 1969) estão associadas ao arremesso de pedras, referindo-se ao episódio em que os judeus no templo tentaram apedrejar Jesus (João 8: 59). Na primeira Frey Pedro Correa (Triumphos Ecclesiasticos, 1617) diz que quem tomou pedras contra Jesus é como «douda de pedras» (foram homens que o fizeram, e as mulheres é que pagam; negrito meu em todas as citações):
Mal pode levar caminho direito quӗ [quem] torce a Ley de Deos, & quando o Povo perdeo o entendimento offendendo a este Senhor , logo fez vontade de seus achaques descompondose tanto que como douda de pedras as toma contra o Filho de Deos , tulerunt lapides ut jacerent in eum;
Na segunda, o Padre António Vieira (1608-97), distingue entre doidos que precisam de ir para o hospital psiquiátrico e os «doudos de pedra» que são os jusdeus que vinham preparados para apedrejar (Vieira Abbreviado em Cem Discursos Moraes, e Politicos, 1746)
E quanto ao juizo , e ao uso da razaõ : Quare, diz o texo que tomaraõ pedras para atirarem a Christo : Tulerunt ergo lapides , ut jacerent in eum. No sagrado do templo nem as pedras eraõ taõ miúdas , nem taõ soltas , que as podessem tomar alli : final he logo , que já as traziaõ comsigo. Vede se mereciaõ ser levados á casa dos Orates [hospital psiquiátrico], pois naõ eraõ doudos , se não doudos de pedras.
Fr. Jeronymo de Belem em Chronica Serafica da Santa Provincia dos Algarves (1753) também parece dizer que um louco de pedras é quem atira pedras:
Nada disto passava por alto ao demónio; pois mal satisfeito da grande guerra , que a serva de Deos lhe fazia , procurou por todos os modos o persegui-la , e maltrata-la. Como louco, de pedras lhe atirava pedradas á janella da casa , em que dormia
Encontra-se na net sem grande fundamentação a tese, reproduzida nas outras respostas, de que a expressão se refere à chamada “pedra da loucura”. Passei em revista todos os exemplos de doudo/doido/louco de pedras do Google Books, incluindo variantes feminina e plural, e em nenhum caso encontrei nada que sugerisse a “pedra da loucura”. Também não encontrei no Google Books qualquer ocorrência de pedra da loucura anterior ao século XX; encontrei algumas pedra da cabeça, mas lendo o contexto, conclui-se que nada têm que ver com loucura. Não encontrei portanto qualquer indício que a crença da “pedra da loucura” tivesse existido em Portugal ou no Brasil.
No Google Books, doido/louco de pedras começa a rarear no século XIX, primeiro em Portugal, mais lá para o fim no Brasil. Depois, a partir de 1969, aparece em força no Brasil doido de pedra, juntamente com alguns louco de pedras.