I can think of a number of different paint media that can create very different and interesting effects.
Acrylic paints are probably the cheapest, most available and obvious paints to choose. They stay slightly flexible after drying, so changes in the leaves' shape due to moisture shouldn't crack them. ModPodge mixed with paints would also work and give the paint more transparency, if that is desired.
Oil paints could probably create interesting effects, especially if you use them like a glaze to enhance the natural color instead of completely covering it. The disadvantage is that oil paints take a long time to dry.
Oil pastels dry a lot quicker but are a lot firmer. You'd need thick and sturdy leaves to use them.
Encaustic is a technique where you melt colored wax onto paper. You could use the same technique to "paint" wax on leaves and it even works well with cheap crayons. This will probably work best on very pale leaves (because the wax is thin enough to show the paper or leaf in spots) and it can protect the fragile leaves from damage. The disadvantage is that the thin layer of wax can crack easily if not handled carefully. And make sure to put a sheet of baking paper between your iron / hot plate and the leaves to catch any spills. Or melt some wax of different colors on this paper and dip the leaves into the molten wax.
Wood stains would probably soak into the fibers of the leaves and look more natural than acrylic paints (if you use red wood stain). If the leaves don't have a uniform consistency, you could get patchy results, though. And if the leaves have a waxy surface the stain won't work at all.
Spray paints (as mentioned by fixer 1234) are very good at creating a very smooth and even coat.
I would not use any water colors or aquarelle paints because they probably won't stick very well to the leaves and there's a higher risk that they crack and flake off if the leaves bend or rub together after painting.