How can a company know my coat of arms simply from my last name?

They can't. Any company which purports to supply you with a 'coat of arms for your surname' is misleading you. Coats of arms do not belong to surnames. They belong to individuals, and are either granted to a particular person, or inherited by descent from someone to whom arms have been granted in the past.

Rouge Croix Pursuivant
December 2001