How do I heal land-armies?

Land them on an occupied or friendly planet. This will slowly heal each and every day they are not under attack.

They heal automatically, both when landed on a planet and while embarked.

(This has changed since the accepted answer was posted, they used to only heal when on a friendly planet.)