I am currently working on incorporation of geocaching into an early childhood classroom as well. Prior to my setting out containers for the children to find, they had worked with puzzle maps (Montessori) and demonstrated their knowledge of the cardinal directions and at least a partial understanding of intercardinal directions. Several of them had also made their own compass roses. Although this work is available to children of all ages in our multi-age classroom (3-6 year olds), the 4 1/2 to 6 year olds are the ones who gravitate to it the most.
And yes, with no trepidation I let them take off with my $300 personal GPS unit (after the usual instructions on use and responsibilities) in search of what I had hidden that day. The hard part for me is taking multiple sets of readings on hiding places to average coordinates for each of the hides. Our playground is small, and the children are enthusiastic. That makes it hard to keep up with their interest in caching by setting out new caches on a regular basis. Recently I shared trackable items with them. Tracking items like TBs and GCs online with the trackables' maps would be another way to use geocaching in the classroom (geography). You also could establish some mystery caches that would require the children to incorporate math and other skills. Although my students could not go find the final cache locations for several mystery caches in another state, they enjoyed completing the mazes that enabled them to see the coordinates that I had also determined and used to find the caches myself. We then looked up the locations of those caches in a DeLorme atlas using the coordinates along the edges of the maps (grid system). Field trips, as mentioned in another log, would allow you to visit sites of virtual caches which might have historical or some other cultural value in addition to finding caches that are available through geocaching.com.
Yesterday I did an introduction to geocaching presentation for interested families from our school. It was well received. The children ranged in age from 5-9 years of age. None of the children wanted to leave until they had found all 7 containers I had placed on the campus. Containers ranged in size from a magnetic nano to an ammo box. A few hints were needed to make some of the finds, but once the children and their parents understood the method, they really took off.
Best wishes for an awesome educational opportunity ~