The Pokemon Company did a great job with creating Starter Kits; you get two 30-card decks which are already arranged in an order to help explain how the game works and all the nuances of the rules you'll possibly need to know to start playing. It's as simple as opening it up, each of you taking a deck, and simply reading the rules and following along with them; it's pretty much a live tutorial.
Once you've got the hang of how to play the game, I'd highly recommend going with Rusher's advice in the answer above. Usually, your FLGS (Friendly Local Game Store) or Comics & Cards shop will be more than happy to let you know what's the best premade deck to continue playing and what to look out for in booster packs, as well as advice on how to construct a deck of your own.
You might also get him interested in Magic: the Gathering, as from what I've seen, the rules are only a little more complicated than Pokemon.