How do scientists know that a rock found on Earth came from Mars? There are many documented cases of meteorites being reported as from Mars.

http://en.wikipedia.org/wiki/Allan_Hills_84001

While I can understand that it's possible to know if a rock originated as a meteorite. What I don't understand is how scientists can say it came from Mars with certainty.

How can they verify such a claim, and differentiate between a rock that is similar to one from Mars to one that really is from Mars.
Mars is the only planet providing rocks with a similar chemical composition and age. So the origin of the meteorite is evident.

This doesn't mean, that it's absolutely waterproof. There might have existed protoplanets similar to Mars 4 billion years ago, which since then have been swallowed by Jupiter, the Sun, or have been ejected out of the solar system. But this would be much of coincidence without leaving convincing evidence. (Here a paper about a couple of simulations.)