In order for us to detect it on Mars, it would need to do something that would make us notice because remember, space is really big. The more energetic the event, the more likely we will detect it. A long deceleration burn to put the probe into orbit around Mars would have a good chance of tripping some IR scanning satellite somewhere. Deorbiting the probe in Mars' atmosphere would look indistinguishable from a meteor and likely ignored.
Edit: After reading the "There ain't no stealth in space paper", any kind of deceleration burn would assuredly be detected.
There are satellites that take pictures of the surface of Mars with sufficient resolution to locate various Mars rovers. If the alien's surface probe was as big or bigger than the US Curiosity probe then we should see it after a few months or a year. If the probe has a larger orbital component then we have a decent chance of detecting the orbiter based on its radio transmissions to home (though this may not work if the orbiter is using a tight beam radio transmission.)