Literally, “from the heart”. The form harte is an old dative case form of hart. An even older form, still attested in Early Modern Dutch, was van harten.
van harte