PDA stands for Personal Digital Assistant.
They come in two main 'flavours' or Operating Systems, Palm and PocketPC, and both have their strengths and weaknesses.
Small Palm PDAs are often available second-hand for under $100 and are quite capable of performing all the functions required for paperless caching.
At the simplest level, a PDA can store all the descriptions of a selection of caches, usually a whole State or region, meaning that impromptu cachers have all the data they need with them at all times. They can also be used to take notes on cache finds for later logging.
More advanced models allow the user to display spoiler photos, connect to GPS receivers via cables or Bluetooth wireless, show maps (moving dynamically if connected to a GPSr), and provide ebooks, music and games to help pass the time until the Muggles move away from the cache area!
Waypoint management software lists software suitable for use on many PDAs.
Some PDAs can even store addresses and phone numbers, schedule appointments and keep To-Do lists, apparently...