First up, if you don't know what Geocaching is, then please do yourself a big favour and look at www.geocaching.com
So..., Yes its an iPhone app, andI've been looking/building something similar for a while.
Lots of GPS systems promise Geocaching options but they all seem to fall a little wide of the mark (or the ones that I can afford do)
This could be the answer?
http://www.geocaching.com/iphone/