First of all, the king must rout, otherwise you cannot capture him. Indeed some of the V&V (legendary leader, brave beyond belief, famous warrior, etc) make the king impossible to capture since he will fight to the end, no matter what.

You have to surround and isolate him to lower his morale. The type of troops doesn't matter. It is important to have a fast and fresh unit of cavalry nearby to send in after he retreats. The cavalry will pursue and capture him if he manages to escape.

This tactic is not 100% guaranteed but I found out it works best.