If you've had your cake, haven't you already eaten it? So why can't you have it and eat it too? It doesn't seem to make sense.
I'd be surprised if this hasn't been asked on this site already, but this is a rather contested idiom.
First, the order of the phrases is uncertain. If the idiom was derived from the phrase, "You can't eat your cake and have it to," as some have suggested it would make much more sense. If you ate it, you no longer have it.
Second, the verbs accepted today a) may not have been the original verbs used or b) may have had different meanings. In some early mentions of this idiom, "eat" is replaced with "ate."
Third, depending on your understanding of the structure, the current phrasing may be fine. If I said, "You can't have your cake and then eat it," then of course this makes no sense. I believe this is the thinking of most people bothered by this current phrasing. If instead you view the verbs as having to occur concurrently, then the idiom makes more sense. By eating it, you no longer have it. As you eat, the less you have.
I had heard this idiom for years and didn't understand it until I heard someone translate it from Russian this way:
You can't eat a piece of cake and still keep the cake whole.
When I heard it expressed that way, I suddenly understood the meaning.
It is a metaphor which could perhaps be better worded for clarity. Especially for a non-native speaker, it must be difficult to understand.
It means that you cannot both have a piece of cake on a plate in front of you, all ready to eat, and also to eat it. For once it is eaten, it is gone.
It is usually applied in circumstances where desirable outcomes are mutually exclusive. Let's say I want to take an holiday in June this year, but I also want to stay around to watch the World Cup. I simply have to choose one or the other. I cannot both have my cake, and eat it.
I have heard this statement used as a mild insult.
People say: "You can't have your cake and eat it too" to express disdain for a situation where two things seemingly should go together but, for whatever reason, something is missing and the situation is now awkward.
For example: you work a 40 hour work week and a foreign entity garnishes all of your wages. You may exclaim: "Wow, I guess I can't have my cake and eat it too."
The original version of this phrase (and the one which makes more sense), is "you can't eat your cake and have it too." It refers most specifically to opportunity cost, in that you cannot spend a resource and still hold it reserve; you have to choose one or the other.
Recently, the reversed phrasing, "you can't have your cake and eat it too" has become more popular, and is generally used to rebuke someone who desires any two contradictory things. For example, you might use the phrase when your Hummer-driving friend complains about how much money he spends on gasoline.
This ngram chart shows how the reversed phrasing became the more popular version around 1940:
Interestingly, the Unabomber Ted Kaczynski used the original version rather than the popular one, and this was one of the clues that eventually led to his arrest.