If you are saying goodbye to someone who is staying (you’re leaving their house or place of business, for example), you say this:
안녕히 계세요.
This phrase means, “Stay in well-being.”
If, on the other hand, you’re saying goodbye to someone who is going away (they’re leaving your house or place of business), you say this:
안녕히 가세요.
It means “go in well-being.” If you meet someone on the street, you're both leaving after the conversation is done, so you use this second phrase.