Shrinkwrap mesh onto another mesh
The next version of Blender, version 2.78, currently available here https://builder.blender.org/download/ will contain major improvements to the Grease Pencil. With these, you could get a really fast starting point for your example. The new release allows you to define specific brushes for GP, and also to smooth the stroke, which is what I'm using in this example.

First, enable the options like this (note that this is only available in the release stated earlier) and draw the curve onto the mesh directly by holding down the D key and click-dragging:



The smoothing option will, as soon as you let go of the mouse, smooth out the stroke, cleaning it up and making it usable for the next step.

Then, convert the pencil drawing to a curve:



Finally, add some bevelling, subdivide the mesh, and set the smoothing option: