Well, the Linseed oil and colouring pigment from a paint shop works, but it is a pain as the pigments sit on top of the oil, the oil takes an age to dry. in the end I varnished over it. There has to be a better way!. Not happy with the results, will probably put it in in a corner and make another! Nice ornament. I did not try using artists oil paints as a pigment.

Here are some other suggestions I have picked up from the net..

1: Rustoleum has good reports.
2: Varnish and use artists oil paint for colouring the varnish. Good reports.
3: Use blood! From an animal presumably! It stains the wood, apparently has a basis for authenticity?
4:Shoe polish. I have used this in another arena and it gives a pale, but stained covering of the wood. Cant really think it would do a good job on such a large expanse as a paddle. I may well be wrong and it depends on what you want to achieve.
5:Fruit staining. Wood chip/bark. Boil the fruit/bark and reduce it to a thicker concentrate. Very old fashioned approach. Lace bobbins in wood and bone were beautifully dyed using these methods. They actually boiled the bobbin with the bark/fruit... cant do that with a paddle.
6:Leather dyes. Sounds interesting.
7: Blow authenticity and paint the darned thing!

Depending on the wood you use i think leaching is a problem. i have a cedar/pine laminate. the pine does not bleed but the cedar does.