This is rather tricky. Had the question read:
I was surprised that they had __ decided what to do.
then the answer would be already.
There's no simple answer to this question, partly because of the different ways the word yet can be used. Macmillan lists seven definitions for yet, along with three phrasal uses. It's one of those phrasal uses being referenced in the test question:

We could add to that list of examples:
I am surprised that they have yet to decide what to do.
As to your question about the differences between the words, some of their meanings can be very similar. (NOAD defines yet as up until the present, while defining already as before or by now – that's a very subtle difference!) However, other usages of the two words differ. For example, if I said:
Have the guests arrived yet?
that would imply that I don't know whether or not the guests have arrived. But if I said:
Have the guests arrived already?
that would imply that I realize the guests are at the doorstep, but I'm a bit surprised by how early they've arrived. Why the difference? NOAD lists this additional meaning for already: as surprisingly soon or early as this.
There are additional ways the two words can be used, yet I can't list them all here.