According to the Word Detective:
There is general agreement that the first use of "teetotal" in reference to abstention from alcohol was in a speech to an English temperance society by a man named Richard Turner in 1833. Whereas some of his contemporaries drew a moral distinction between beer and hard liquor, Turner urged his listeners to abstain totally from all alcohol.
Contrary to popular legend, there is no evidence that Turner recommended "tea" as an alternative to alcohol, or that his listeners were urged to mark the letter "T" for "Total Abstinence" on their pledge cards at the meeting. The "tee" tacked onto the front of "total" was just a common way, at that time, of giving extra emphasis to a word, a process linguists call "reduplication." (And yes, the term "reduplication" has always struck me as weirdly redundant.) The use of "teetotal" to mean "absolutely, totally" is well-documented in other, non-alcoholic writings of the day.