Mithridatism is an actual practice that is possible with biologically complex poisons that react with the immune systems. The mechanism is similar to that of developing immune resistance to a disease or allergen, a matter of training the body to use the immune system to eliminate the poisonous compounds before they can harm you (or, in some cases, conditioning the immune system to not react, as with allergens, as it is the reaction that is dangerous rather than the compound itself). The poison, not having an effect, can be naturally eliminated from the body. The process generally does not work with non-organic poisons, which will instead accumulate in the body, and some organic poisons act on other mechanisms, which means the immune system is not in the loop. It is possible to develop a tolerance to non-organic poisons through repeated exposure having the liver provide larger amounts of the enzymes necessary to destroy the poison, but as seen with people who develop alcohol or painkiller resistance, this is generally acquired alongside liver scarring.
In almost every case, it's tolerance that you develop, not immunity, and it will not work generally against all poisons, so the answer to your first question is "no" with the caveat that it can work with some poisons.
As for a specific poison that might have been the one that he developed an immunity to, arsenic is sometimes cited. It was a poison that the Romans has access to and it is one of the poisons one can develop a tolerance against with gradual dosing.