Buy him a copy of C Primer Plus (5th Ed) by Stephen Prata and work through it with him. In my opinion it is one of the best introduction to C books available, if not the best and very friendly to first time programmers. Another option is Java: A Beginner's Guide (4th Ed) by Herbert Schildt.
I too believe that learning the lower level things such as memory allocation is the best way to make yourself a better life long programmer so I would advise C over Java however I know a lot of people who only know Java (or C#) and do just fine however they knew next to nothing about what I consider to be "real" programming. Everything they do is drag and drop then writing some logic to handle an event and letting the runtime deal with the "nitty gritty" stuff.