They're really creases, not true "folds" so the secret I've found is to not try and form them on a flat surface the way you would a straight fold but, instead, fold them in mid-air using your fingers (and nails if you have them) to support and shape the creases.
- start a crease in the direction you want (mountain or valley) by bending the paper in the desired direction but do not attempt to fold it flush.
- use your thumb and forefinger above the paper to create a crease with the middle finger in the crease below it to keep the paper from collapsing completely.
- shape the curve as you move along the paper.
- go slow and be patient
If you want to make really detailed shapes, consider etching the creases in first with a tool.
I found it was easier to start in the center of the curve and work outwards in both directions to achieve the curved shape.
Here's a video showing the process... note that, in this case, the creases are pre-etched in since this is a purpose-made piece of paper but you should be able to use the same method without the pre-etching.