All have different meanings.
Trace: to ask various people for information about someone's whereabouts and eventually locate them from the information you have obtained. This could happen days, weeks, months, or years afterwards. You could be anywhere in the world.
Trail: to follow in real time someone who leaves visible indications of them passing through recently. ie. In the Lone Ranger, Tonto would trail someone by the horse's hoof prints. This could only happen within a few hours or days, but you need to be there to do it.
Track: to follow someone from information they leave as they move, eg you can track a parcel through the post because someone records where it was at various stages. You don't need to be there, you just gather the information.
Shadow: to follow immediately while in sight of the target, while keeping yourself hidden from view. This is close...you are effectively the person's shadow that they can't see.