How do I add veneer stone to an exterior painted wall?
You need mesh. While veneer is a fraction of the weight of full stone, it is not light. The mesh forms a framework that the bonding material will surround and be inseparable from it (absent smashing with a hammer). The mesh is firmly attached to the underlying structure with fasteners (type depending on the nature of the siding).

In this case, the painting of the surface makes no difference.

Getting mortar to adhere directly to an existing concrete, stucco, brick or stone surface is not simple, especially when there is a tendency of the attached material to pull away from that surface. Adding to a horizontal surface (like a concrete floor, steps or walk), there is mostly a compression force (pushing the surfaces together), and bonding makes more sense. On a vertical (or overhead) surface, where the force is tension (pulling away), this makes less sense.

I think you need the mesh.