This is a good place to start:
In fact, if you go to adafruit.com and browse the Arduino section, there are a few starter kits to choose from, and a whole list of add-on packs that will give him an easy introduction to whatever technology floats his boat: GPS, Bluetooth, audio, robotics, etc.
The things to look for are as follows: The Arduino board itself (Uno), at least one decent size breadboard for placing parts, a bunch of jumper wires, and a reasonable assortment of things to plug in.
Examples of the latter include resistors, LEDs, buttons, and knobs (also called pots, or potentiometers, or variable resistors) at the very least. Also nice are light and infrared sensors, motors, servos, temperature sensors, transistors, 2-line character LCD, maybe a solar cell, a little speaker, relays...
Checking off all these things isn't important, as they're easily sourced from the same site, hobby shops, electronics supply stores, or any number of other places online. No kit will have all you'll ever need, so further parts orders are inevitable. The key is to have enough parts to play with that you can run through some of the examples that come with the Arduino, and to have a collection to fall back on when you want to experiment down the road.
A good idea might be a starter kit like the one above, and a gift card to Adafruit or Sparkfun or similar, so he can pick up whatever else piques his interests.
I would recommend staying away from the more exotic Arduinos (the Mini, Mega, Yun, etc..) until he's had a chance to play with the Uno for a bit. When you're just starting out, your impressions of what you're going to "need" (in terms of hardware) are usually off, since you don't yet have a good frame of reference for what these things do. The Uno is a really great starter platform. It's cheap, ubiquitous, capable of quite a bit, and otherwise just the Goldilocks of microcontroller development. The other boards tend to fill specific needs rather than improve on the Uno in any substantial way -- at least for general purpose tinkering. Basically, when you reach the point of needing something else, you'll know, and have a better idea where to go next.
BTW, you're awesome for doing some research on all of this. He's a lucky guy. :)