First of all, it's hard to answer questions about GPS units without knowing which one you're talking about. The most basic types really just tell you what your longitude/latitude coordinates are, and will tell you which direction to travel in to get to a specific set of coordinates. The more advanced ones add all sorts of features and gizmos, such as a display that shows a map of the local area and where you are on it.
Of the ones that have a map display, a lot of GPS units will have a basic map built into them. For more detail, you can buy mapping software on CD-ROM and download the maps you want into your GPS unit, depending on how big its memory is and whether or not it will interface with you computer - but most of them will these days. The CD-ROMs can get pretty expensive. Garmin's
Mapsource US Topo series, for example, will run you about $100.
Now geocaching is... well, the Wikipedia entry on
geocaching explains it a lot better than I can.
As far as accessories are concerned... as I mentioned initially, that really depends on what kind of GPS you get. If you get one of the cheaper units that really just tell you your current coordinates, then you'll also need a topo map of the area, a compass and a protractor so you can turn those numbers into a position on the map. If you get one of the GPS units with a map display built in, you really don't need anything but a compass and the GPS.