I would definitely pack the following:
- GPS receiver - this may be your phone if you're starting out, but a dedicated receiver really does wonders if you're looking at Geocaching often. They're more accurate and don't eat through batteries as quickly. If you are using your phone, packing a cheap spare may be wise depending on where you're going - you don't want to use up all the battery, then land yourself in trouble and not be able to phone anyone.
- Spare batteries for the above; if they're rechargeables make sure they're fully charged and not worn out. Personally I use Eneloops, they hold their charge for a good length of time.
- Printouts of locations and clues to all your caches; even if you've put them on the GPS I find it much easier flicking through clues and logs on paper. Don't forget to look at recent logs as well especially if you're stuck which might offer more of a clue.
- Pen / pencil. Take multiples, and don't take expensive ones. They have a habit of going missing since they come in and out of the bag a lot, the pack of 8 cheap as you get pens at the local stationary shop will do just fine.
- Tweezers. Incredibly useful for extracting tiny logs from nano-caches.
- A couple of (again, cheap is fine) spare pads / rolls of paper. If you spot caches whose logs are full, it can be a huge help to the cache owner if you leave a bit more paper until they get around to replacing the log.
- Torch (known as a flashlight in the US). Essential if you're night caching, but very useful to have either way. Great for peering in dark places that caches might be hiding in!
- Camera. Not essential, but Geocaching can often take you to new and cool places, often when you least expect it! I've wished I've had my camera with me on several occasions.
This is not necessarily an exhaustive list at all, and I'm only counting things here that are directly relevant to Geocaching. Obviously if you're after a cache in the middle of a cave you'll need additional suitable equipment, and the associated caution and expertise. Additionally, things like first aid kits, food, etc. would be sensible if you're venturing out a way, but the list above should serve as a good "geocaching-specific" checklist of some things to take along the way.