I don't know what the general rules are. I agree with the other answer that in many cases you can either use that or leave it out, and it doesn't change the meaning or grammaticality. But I think I can help answer for the example you gave. I think it is somewhat of a special case. The phrase "I'm afraid [that]" has two different meanings:
- I feel fear that it could be the case, but do not know if it is or not
- Unfortunately, it is the case that
In your example sentence, it's clearly the second meaning, because the speaker knows it to be true. They're expressing their regret, not fear.
Each of these meanings can be expressed both with or without the word that, but I think the word that is used more often with the first meaning than with the second. That is, if you want to say:
Unfortunately, your luggage is overweight.
It is more common to say:
I'm afraid your luggage is overweight.
You can say it like:
I'm afraid that your luggage is overweight.
But when I see or hear that, I'm likely to think of the first meaning, where the speaker is unsure and feels fear.