Citrus oil has worked wonders for me in deterring cats from the flower beds in my front lawn. I don't want to use anything that could hurt my plants or the cats although they are annoying...
If you have pine nearby you can try small cuttings around your yard too. There's a blog post I found that was very useful, I'll try to dig it up.
