I found by digging over soil and making it nice and fresh the cats instantly homed in on it - as they still do whenever I try to do a bit of gardening and head straight for the new plants I've just put in!
Both my cats are 9 years old, and this year have been terrorised by a stray, so started toileting indoors again after all this time, so I had to bring the litter tray back! But slowly I've managed to persuade them back out by spending more time outside with them, and gradually building their confidence again. I find by digging over patches of soil with big plants growing around them gives them a bit of cover so they feel less exposed and more amenable to using the garden to toilet in too.