The sheath on the right (which I made for this knife) is made from vegetable tanned leather, and originally was the same color as the piece on the left. I put it in a vinegar and iron oxide solution, similar to what is described here, overnight and then took it out to dry for a couple days.

For me, the cost of the dye was zero in both money and effort. I have a small tub of vinegar in my shop. I use it for removing rust from old tools when I do not want to bother with electrolysis. By now it has quite a bit of Iron Oxide in it. I simply used that for my solution.