THIEVERY DAMAGE = (1/2 speed stat) x Number of successful steals.
So you can increase his Thievery damage by eqipping him with things like Thief's Hat and Thief's Gloves. Once you steal enough get him up to quad-9 damage, you can equip him with whatever.