Our first find was in March 2007 in Frauenstein, a small town just outside of Wiesbaden, Germany. My wife had heard of geocaching from a friend of hers and suggested we try it. I had previously heard of it in the early days of geocaching but had not bothered to find out any details.
We had previously attempted the closest cache to our apartment, an urban micro that turned out to have horribly inaccurate coordinates and a cryptic hint that we never did understand. We also were caching using a Garmin GPS 12, which was not terribly accurate and did not show anything other than distance and direction.
Our first find was GCX209, Goethestein, a small cache in the woods. I remember we went down the trail and when we got close I made the rookie mistake of relying on the GPSr and not in just figuring out the general area and then looking around. I remember getting frustrated by our inability to find it, and then finally getting excited when we spotted it. That was also our first travel bug experience, which was fun. We found three other geocaches that day aroud Frauenstein, and we were hooked.
Not long after, I ditched the GPS 12 for a much more accurate 60CSx, which made things much easier. It was still a challenge caching in Germany at first, because I didn't know much German, but it was a great way to learn it.