C:Geo is good for live searches, but it violates the TOS of Geocaching.com. I'm fairly certain that nobody has been banned from the site for using it though.
Geohunter is another great app. This one uses PQ's that you generate from the web site. It doesn't do live searches like C:Geo does, but it also doesn't require a connection to the internet to get your data, the database is stored on the phone itself. Both apps are free, so why not try out both?