Well, first you're going to need to strip the surface finish back - if it's got sealers or polishes on there, the only thing that is going to do the job is a solvent. Might be worth cleaning the thing with saddle soap first, depends on what state it is in. Then attack it with a cloth soaked in isopropanol or (more aggressive) acetone - wear gloves (and make sure they'll stand up to the latter if you use that). Hopefully, that'll deglaze the surface adeqautely to allow the new dye to penetrate (it'll also strip out some of the dye, but not enough to be useful).