One of the earliest references you can find was a group of black soldiers in the 1890's. Known as the 25th Infantry Buffalo Soldiers, these guys were probably in better shape than most of us are today.
The Buffalo Soldiers were based in Missoula, Montana and rode single speed bikes that were modified for long distance travel with supplies over rough terrain. They weighed about 70lbs-120lbs when loaded.
Their two biggest trips of note were a nearly 800 mile round trip ride from Missoula to Yellowstone, and a 1900 mile one-way trip to St Louis, Missouri.
Another well known group of "mountain bike pioneers" was the Velo Cross Club Parisian (France - Early 1950's). This group if cyclists was customizing their 650-B bikes with some remarkable modifications for their time. They had handlebar shifters, fat tires, and even some suspension.
Further credit goes to a guy named John Finley Scott who modified his bike "The Woodsie" in 1953 for fun rides in the outdoors. He too had shifting gears, fat tires, flat handlebars etc.
Although all of these sources sound much like mountain bikes, nothing really ever developed from their efforts.