I learned Spanish in Mexico, where "I miss you" is "Te extraño." However, I've recently been traveling around Europe, and I learned the Spanish phrase for the same is
Te echo de menos.
What is the origin and literal meaning of this phrase?
The origin is linked to the Portuguese way of saying I miss you.
Achar menos means 'feel the need of' or something similar because of the connotation of the expression 'to find someone less than before'.
By extension, this expression was adapted to the Spanish language using the closest verb to replace achar: echar. Which should have been 'hallar' (find) instead. This is of course, a hypothesis, the use of 'echar de menos' has been mutated from the colonial times, where in some old writings the expression 'echar menos' can be found.
The literal translation of echar menos is: 'Throw less' WTF?
I found this resource (with some further links to some references such as RAE, which explains:
The expression is of Portuguese origin “achar menos” and is documented in Castilian Spanish since the 18th century as «echar menos» (without the preposition) although currently it is almost always used with preposition «echar de menos».
The source also claims it has no logic in Spanish, so it is just a calc from Portuguese, but is common enough that it is part of the Spanish language.
I certainly understand it (in Colombia), and use it although less frequently than «extrañar».
P. S. I just saw Daniel's answer and he gives a better description of the etimology in Portuguese and how it was incorrectly adapted to Spanish.
Let me separate by parts to explain the meaning:
EDIT: note that when someone says "Yo te hecho" then he/she is expressing that he is doing the action but is another one who is involved in the action. Let say that I am doing something or I am experiencing something that you are involved; what is this? well, I am feeling the sensation that we are far apart and the sensation that I have missing something, I have lost something that in the past I had, what I have lost? well, it could be the meetings we had, the talks we had, etc.
As an example take the phrase "Echo de menos a mi perro" (I miss my dog; meaning that there is someone -my dog- that is less "something" compared to the past...maybe his dog has dead and he miss to give affect to his dog).
Your question has already been well answered by others, but I'd like to point out a conceptually related phrase and another way of saying I miss you. Namely, "me haces falta", which has the same sense of being less because someone is not with you as does "echar de menos". I find it beautiful in the sense of communicating that I am less because you are not here, or you leave me wanting. I also find it expressive and elegant because of the way it puts the action on the person being missed, so instead of "I miss you" it is "you make me wanting". But I also find that it doesn't literally translate well to English on a word for word basis. Some of the very best ways of saying things in Spanish are rich precisely because they don't translate directly to/from English and thus express nuances that are missing in English.