Once a Pokémon is befriended, you will notice that it has a percentage near it. This is the link it has with the Warlords. When you befriend the Pokémon, it will likely have a low Link level. However, you can increase this link with the trainer. You can check the link once you have befriended them with a Pokémon and can always check repeatedly within the "Collection" menu.
To increase the link between Pokémon and Warlords, all you need to do is enter a battle. Battles with normal wild Pokémon give the lowest increase, wild Warlords give a slightly increased amount and massive battles to take or defend a nation provide a larger increase. However, you may notice that the increase will stop at a certain point. This is because they are not that compatible. Pokémon tend to be more compatible based upon the type of Pokémon they are and the type the Warlords specialise in.
Link affects more than just the strength listed on the overworld. It affects the stats of the Pokémon including Hit Points, Attack, Defence and Evasion.
Finally, evolution will occur once the Pokémon reaches a specific link percentage providing it doesn't require an item to evolve.
While the majority of the Pokémon will have a maximum link level of anywhere between 40% and 98%, for each Warlords, there are a handful of Pokémon which will be capable of having a 100% link with the leader. Each leader will only have up to three possible Pokémon that match this, and they typically completely match the type upon which the Warlords focus. Click here for a list.
Once you have befriended the specific Pokémon, the Warlords will tell you that you have found them and will recommend raising it to the maximum level. This will make the Pokémon as strong as it is capable. Once done, it will also be added to the Collection page for the Warlords and listed under the "Completed" aspect. Do note, however, that some Warlords have middle evolutions as their Best Link Pokémon, and evolving them may push the link down. An example of this is Ginchiyo who has a Best Link with Luxio, but when it's a Luxray, it's 98% until she ranks up
There is another perk to reaching the high link with the Pokémon. Once you do, the Warlords will offer a chance for them to "evolve". Doing so will change their appearance, and like with Pokémon, increase their stats.