How did "next day" come to mean "day of next week"?
Solution 1:
This use of next Tuesday to mean Tuesday of next week is fairly old, according to the Oxford English Dictionary. They include examples under the definition:
Applied (without preceding the) to days of the week, with either the current day or (in later use; orig. Sc.) the current week as the implicit point of reference. Thus (for example) next Friday may mean ‘the soonest Friday after today’ or ‘the Friday of the coming week’. The latter may be indicated contextually, e.g. by contrast with this, but it is not always clear which meaning is intended
a1592 R. Greene Frier Bacon (1594) sig. B, Thou knowst next friday is S. Iames, And then the country flockes to Harlston faire.
So the use of next --day came after 1592. However, there is another use of next with a weekday that predates this:
c1390 Chaucer Miller's Tale 3518 Now a Monday next, at quarter nyght, Shal falle a reyn.
There is also this:
c1230 (1200) Ancrene Riwle (Corpus Cambr.) (1962) 211 Ȝef‥ȝe ne beon nawt ihuslet i þeose isette tearmes, beoð hit þe neste [a1250 Nero nexte] sunne dei.
Having traced back the references in the OED, it is possible that the form next --day is a fairly original structure. Next has been used to mean "Designating the time, season, etc., following directly after one described, spoken of, etc." in both early and late Old English.
The OED does note that next with a weekday is:
Applied (without preceding the) to days of the week, with either the current day or (in later use; orig. Sc.) the current week as the implicit point of reference.
So next Tuesday originally meant the Tuesday after whatever day today is, but there is no clear notation of when the additional meaning was added. The use of Tuesday after this current week was noted in the OED as being used by 1711.
Solution 2:
Why did English start doing this? See simchona's wonderfully detailed history of this linguistic convention.
Why does English keep doing this? This convention is sustainable because if you want to refer to the Tuesday of this week, you simply say "Tuesday" or "this Tuesday". Conversely, if you go to the trouble of saying "next Tuesday" I understand that you're explicitly not describing the Tuesday of this week.
PS. "Next Tuesday couldn't be the same as this Tuesday, you know."