From a pastor-friend:

Given that much of the early Church lived in areas lacking in water, the problem is one they already dealt with.

Following is an early church text from "the Didache" or "The Teaching of the Twelve Apostles" - an anonymous work dated somewhere between 70 AD to 150 AD. I scanned it from Holmes revision of Lightfoot and Hamer, The Early Church Fathers, 2nd Edition (Grand Rapids, MI: Baker, 1989), p. 153. There is a link to an online version below.

7. Now concerning baptism, baptize as follows: after you have reviewed all these things, baptize "in the name of the Father and of the Son and of the Holy Spirit" in running water. But if you have no running water, then baptize in some other water; and if you are not able to baptize in cold water, then do so in warm." But if you have neither, then pour water on the head three times "in the name of Father and Son and Holy Spirit." And before the baptism, let the one baptizing and the one who is to be baptized fast, as well as any others who are able. Also, you must instruct the one who is to be baptized to fast for one or two days beforehand. (Didache 7:1-4)

I will add only the remark that in verse one "reviewed all these things" seems to refer to the previous discussion on Christian ethics/morality. It seems that the idea was to baptize only people who could demonstrate commitment to the Christian life.

Lightfoot's translation of the Didache online: http://www.earlychristianwritings.com/text/didache-lightfoot.html