The Oxford English Dictionary gives the explanation that the word was first used by a working man, Richard Turner of Preston, in a speech in 1833. He was advocating abstention from all alcohol not merely from spirituous liquor. They say the word was made by the reduplication or extension of 'total' and so is not a reference to tea.This was done for emphasis. An example is the first meaning of 'teetotally', which is 'entirely, wholly '( in dialect and in the US) e.g 'I'll be teetotally damned if that ain't the limit !' This dates from the early C19 . It's quite likely that that came first and Mr Turner made the adjective from it; it would fit his message, that abstinence from liquor was not true abstinence, total abstinence. You had to be was being completely, wholly, 'teetotally' abstinent (not just from liquor but from beer too).