Ravens as messenger birds is a Song of Ice and Fire innovation. Pigeons, however, are time honored messengers. But there's no training involved. Communication by pigeon relies on the birds' homing instinct to their nests. That is, you take pigeons with you on the road, and use them to carry messages back to your departure location/their nest. In the medieval Islamic world, it was commonplace to carry rather large numbers of pigeons, to prevent loss of messages if they were shot down as game in transit.

Here's an earlier thread on the matter!