You need to start by associating an certain area of your yard with the litter box. Whether you use some of the cat litter(disclaimer: I have no idea about what environmental effects this would have), or if you use sand or loose dirt like Oldcat suggested.
If you don't want to keep a section of litter or sand in your yard/garden, you can slowly start to take it away as your cats become accustomed to going in that spot. Just be sure that you keep the dirt in that section loose,,or slowly switch the sand out with soil. I can't imagine your cat's will want to go in packed dirt.
It will take some watching, but you can train them the same way you would a cat that's refusing to use the litter box inside. Every time you catch them going outside of the "litter box" section, pick them up, and place them in it. Associate the area with doing their business. If you want, you could even plant some of their old business in the area, so they know that's what it's for.
As nice as it might sound, there are some drawbacks to having your cats going in a certain area of the yard. You will still have to clean it occasionally, unless you designate a fairly large area for them to use, it's not going to decompose fast enough to be feasible without occasional cleaning. There's also the risk of the feral cats in the area using it, adding to the mess, and even possibly deterring your cats from using it.