According to this Wikipedia article, the Union Pacific Big Boy locomotive, with tender car, was about 175 pounds per horsepower. Supposing that's not too far off, and supposing you only needed 10 horsepower to push this thing, you would need to carry about 1 ton of engine. You would need to factor in something about impeller blades, fuel, and water as well. So, using the numbers from Slarty's answer, you would need something like 130,000 cubic feet of balloon just to carry the engine. That's a 62 foot diamer balloon just for the engine, no cargo or passengers.
According to this web site relating to the Chester County Balloon Festival, hot air balloons range from 19,000 to 200,000 cubic feet. You would have about 1000 pounds left over with the very largest. So you would need something in the range of 70 foot diameter by 100 feet tall.
Steering a balloon is a challenge because the structure is just a big bag. You would need to put in some allowance for some kind of structure to the balloon. Supposing you changed over to some sort of dirigible. According to this web site on dirigibles, the weight of the dirigible is something in the range of 40 percent of the weight it can lift, using Helium. (Very rough figure.) So with hot air it will be less. So you would probably have to double the volume again to put in some kind of structure. But you could likely make quite good speeds with such a rig.
On the other hand, I have never heard of anybody operating a "hot air dirigible." So maybe there's some technical issue with such a thing that I have not thought of.