Sometimes, as you start a new day on the overworld during the Special Episodes, some characters will come up and tell you that a mysterious Pokémon has been seen around the specific nation and that a new area has appeared holding this Pokémon. This nation, like when a swarm comes, gets marked with an exclamation mark for the turn.
Enter the nation and a new area shall appear. This area will just have this legendary Pokémon within it and will allow you to enter the battle.
That is how to find the legendaries, now to obtain them.
Once you're in the battle, you will face only the Pokémon. This may be your only time to befriend the Pokémon so be sure to bring the best Warlords who fits the Best Link for it. Simply go into the battle with the Pokémon and Link up. This will allow the Pokémon to be yours once and for all
Just be careful not to let this slip past as the chance may not repeat itself.
Source, as well as a list of obtainable legendary Pokemon.