They didn't. You can't tell messenger pigeons where to go, they simply go back home. That's the trick. You raise homing pigeons in a specific location, they grow up there, it becomes their "home" location. To use a messenger pigeon you need to put those pigeons in cages and then carry them with you. The process of sending a message is simple: attach a message to a pigeon, then release the pigeon. The bird will fly back to its home, someone will notice the presence of a bird with a message attached and process that message. Tada, message delivered.

This means that typically your choices of where messages end up is very limited. For example, in war you cannot simply deliver messages by pigeon to wherever the local rear echelon command facility is. It also means that if you want to deliver messages to multiple locations you need multiple groups of pigeons. As it turns out, it doesn't take long to raise pigeons so you can have multiple pigeon stations in a theater of operations over a multi-year war. But you need to be careful about where you place your pigeon stations, if there is a risk of losing control over the territory where the station is located then that could render all of the pigeons who have that as their home useless to you.