Here is a slightly simplified tutorial on how I created the (hopefully) natural looking paint effects on my Taking Of Christ image. If you have a go at this and come unstuck anywhere - send me a PM and I'll be happy to help.
You can create these effects either as a combination of effects from several different packages or by replicating the stages just in Photoshop. Personally I prefer to mix them up as software like Painter & SketchBook tend to have more intuitive tools for brushing on natural style effects.