I read a thread about this already, and it was closed after 4 posts as the poster felt the answer was satisfactory. I would like to point out that in fact the answer was the reverse of the actual meanings.
Although the words are used interchangeably all the time, there is a definite difference.
Fate is a religious term (or spiritual, not necessarily organized and defined by any church) and means that an event or person is a prisoner to it, everything is predetermined. If you have a particular fate, nothing can change it, everything you do is part of that fate. Even if you find out about that fate (which you cannot), that itself was in your fate. It is unchangeable, the opposite of free will.
Destiny on the other hand is something that one makes for myself, or declares to oneself once achieving some goal. For example, one can say "I'm destined to become the best fighter in the world", and then work on it to make it so, destiny has far more in common with a goal than fate. Once the person becomes a great fighter, he/she would say, "I was destined to be the best, nothing could stop me". That being said, if such a thing as fate existed, and this same person was fated to become the best fighter in the world, it would happen no matter what actions the person takes, but these actions are ultimately predetermined already in order to make the end event happen, this person may never think about fighting but find himself being the best after 10 years of cause and effect (which is also the case in destiny, but no predetermined).
Fate is like luck, it doesn't exist, but it makes people feel better about certain things. Like if you drink and drive and have an accident and kill your friend yet you survive, you could console or destroy yourself by saying it was fate, some deity or powerful entity controls events and this was supposed to happen, and from that you can either pick yourself up and redeem yourself or go into self destructive behaviour, but either way you're subject to fate if that is what you believe, no matter if it exists or not. But you would never say it was destiny in order to feel better, you may say that because you drink and drive and know that eventually this was going to happen, so you were destined to get in an accident. You create your destiny, fate is something that is only meaningful to those who believe in such things.
Another example is Prince William, he is destined to become King due to his bloodline and because he's young and second in line, but this may not happen, and if it doesn't due to some tragedy, many people may say "it was fate" for obvious reasons.
In simple terms, fate is a belief system that we're puppets to a grand plan and design and have no free will, and destiny is a personal or group journey, and is changed to suite whatever purpose whenever it needs to be.
Most religions have both free will and fate intertwined in their sacred texts, but the paradox is fine, even the universe itself has this paradox. As an astrophysicist, it is still an incredible thing that this paradox is very real, everything that happens is due to very specific variables and is predetermined, but at the same time even the most tiny of particles can escape this rule via quantum events, let alone conscious life forms like ourselves (we are also subject to quantum effects, however small and un-noticed), so we live in both an universe of fate and free will, and they are indeed the same thing (however this is not a religious concept, but rather a scientific one, so perhaps a better term than "fate" is needed)