I liked this book when I was younger: https://www.amazon.com/Transition-Advanced-Mathematics-Douglas-Smith/dp/0495562025. It will help him make the jump from what's typically available in high school to what he'll encounter later. People are recommending Spivak's calculus, which is awesome, but I'm glad I had the one I linked under my belt before reading Spivak.
All I know is that they're no longer doing Fitzpatrick or Chartrand (according to what a professor told me). Here's the new book. I think it's possible the course will be less analysis-focused. I think they should incorporate some abstract algebra into it. This goes into effect next semester by the way.
Usually, math majors in undergrad take a bridge course that teaches you how to prove things in general, without getting too much into technicalities of individual subjects. For instance at my university it was taught out of http://www.amazon.com/Transition-Advanced-Mathematics-Douglas-Smith/dp/0495562025/ref=sr_1_1?ie=UTF8&qid=1448910043&sr=8-1&keywords=douglas+transition They teach some basic logic, basic set theory, functions/relations, and cardinality, which are all useful everywhere in mathematics. The rest of these courses (and the book above) is an introduction to one or more math subjects, like real analysis or group theory. If you prefer you can skip these sections and instead move on to a book that actually covers those topics themselves. That said, the introduction can be nice for giving you a feel for the subject before you dive into too much of the details.
If you already have particular interests, in some cases you would be better off just pursuing them right off the bat. For instance if you are interested in graph theory, that is fairly approachable without prior training.
This is the book I used and I didn't think it was as bad as the reviews make it out to be. Could be I had a good professor too. I think that if you are trying to work your way through a book by yourself this one wouldn't be too bad, but checking your proofs for accuracy is much harder than in a computational maths class. If you are planning on doing that get one of the older editions. It's basically the same book except $100 less.
Reading the comments it seems that a lot of people never had a specific course on learning to do proofs and that could be because most schools don't use an in depth calculus book (but how many schools out there don't use Stewart these days?). Here at my school we have a required course called Discrete Mathematics which goes over numerous proof methods, which I found to be one of the best classes I've taken and if I had known how helpful it was I would have taken it much earlier than I did.
I would say start with learning how proofs work. They can sometimes be confusing at first and (in my experience at least) calc doesn't do a great job of explaining them.
I learned from a book called A Transition to Advanced Mathematics it's been around for years, I know you can find copies of it for ~$5 without much trouble. It's got a good introduction to basic proof structure and ideas as well as dipping it's toes into combinatorics, algebra, analysis, and topology.
Another book worth looking into might be Book of Proof I personally don't have much background with this book, but it's the one used by my old university for their introductory course to proofs.
The book that was used in my Intro to Proofs course was A Transition to Advanced Mathematics by Smith, Eggen, and St. Andre. Maybe the difference in presentation will make things click, but what I think might help better is a course or lecture series - like this for example. Both Book of Proof and the textbook I used start from what I'd call the basics - sets and propositional logic. Most textbooks will.
You might also want to look into materials for Discrete math courses. These tend to be courses mainly going over logic and sets, and are what a lot of students take before their Intro to Proofs course. That extra focus on those topics may be what you're missing.
http://www.amazon.com/Transition-Advanced-Mathematics-Douglas-Smith/dp/0495562025
I took a class that used this book my freshman year. It's written very humbly, you can go through the whole book with no prior experience with college math.