I am afraid it will be hard with a Celeron, but what kinds of games does he want to play? Call of Duty: Modern Warfare 2? World of Warcraft? Sims 3?
If he wants to learn about computers, I have a free idea. Go to some local computer stores (not the large retail chains, but a small, local shop that builds and repairs PCs). Ask if he can see their "boneyard" where they put old computers. I was recently looking for a couple components and went to a local shop. Never had been there before. The guy at the shop couldn't have been happier to have someone offer to take some old systems off his hand. He had a back storage room, no heat, no electricity, where he had 15-20 PCs that no longer worked for whatever reason. He said I could take whatever I ended up taking two computers, with hard drives, motherboards, video cards, DVD drives, basically everything but RAM. I'm sure they won't work as-is, but your nephew could possibly salvage a better CPU, video card, and maybe some other useful components.
If you're going to spend money to upgrade the Celeron, RAM will probably be easiest. Just about any video card will probably be faster than the CPU, so he won't realize the full benefit of the new graphics card. If you do buy RAM, get it soon. I've seen some memory prices double in the past month, and this time of year it typically gets worse.
Good luck!