How can I treat leather with dyes and keep it protected?
The general order for treating leather, or at least the one which I use, is as follows:


Cut and shape the raw leather. As enderland pointed out, untreated (veg tanned) leather becomes quite supple when soaked and will retain it's form when dry (this technique is known as wet forming, and is probably how the sheath in your picture was shaped). 
Dye the leather. For veg tanned leather water based dye will work just fine. I don't know much about other brands, but Fiebing's dyes have always worked well for me. Remember to wear gloves, as leather dye is unsurprisingly good at staining skin. 
First soak the leather in water, then apply the dye with a rag or sponge. Soaking the leather first will help the dye to penetrate the leather deeper, instead of just staining the surface. This step is of course optional.
Finish the leather. There are different ways to do this, but the general idea is to work oils into the leather to stop moisture soaking in and rotting it. The traditional method (and the one which I use) is to polish with dubbin, a mixture of oil and beeswax. You'll find that the leather softens a great deal when the dubbin is worked in.
Finish the edges. You can use Edge Kote, but burnishing with dubbin/pure beeswax and an edge slicker also works. This step is also optional, and you can do it before finishing the leather if you want to - it makes no difference. 
Assemble. Leaving assembly until after all the parts are treated makes it much easier to ensure that you've definitely got into all the nooks and crannies of whatever you're making. 


The pair of images below show before and after photos of this process, from a recent project of mine. I'd post more (and links to other resources) but I don't have enough reputation.

My leather is probably darker than yours, but that won't be an issue. I used Fiebing's Cordovan dye, undiluted, and dubbin to finish.