By coincidence I was pondering this a couple of weeks back, and I gleaned this snippet from the Oxford English Dictionary third-hand off alt.usage.english:
The term “lieutenant” is in origin an adjective – the man who holds (tenant) a command or position in lieu of (and as assistant to, by implication) a superior officer. The existing Army rank is short for “lieutenant captain” – i.e., the officer ranking below the captain who serves as officer in lieu of him for a part of his troops. Lieutenant general and lieutenant commander (Naval) are related forms.
Compare the high public office in many states and provinces of Lieutenant Governor – i.e., the man or woman who serves as Governor in case of the death, incapacity, travel outside the area, of the Governor (and in Canada, as the Queen’s lieutenant for her Governor-General, as the “head of state” of a political subdivision).