It's one of those things that's really hard to learn without interacting with another human that already knows it. The root problem is the slow batch-process nature of conventional schooling, where you hear something one day, do the homework the next, turn it in the next, and five days later get it back graded, meanwhile having been expected to do another assignment or two. It's a miracle anyone ever learns it under those conditions.

Most universities have a course specifically geared towards proofs, including first order propositional and predicate logic, set theory, basic proof techniques, etc. I've taught this particular course a few times when I was in academia, and one of the better books that was around at the time (2004--8) was Krantz's _Elements of Advanced Mathematics_.

Also, the initial dialog in _Proofs and Refutations_ by Imre Lakatos is a nice discussion not only of proofs, but on thought processes that one often goes through during mathematical research.

Books that build on foundational axioms and go on to prove or derive theses/theorems out of them are helpful in your case, since they show you proof construction in action. Pick a classic, something that everyone is familiar with but at the time of its writing it was revolutionary. Euclid's The Elements come to mind.

I can't recommend Euclid's "Elements" with enough emphasis. It really is an amazing book. It gives you a set of ~20 definitions, 10 axioms and then goes on for hundreds of pages constructing proofs using those axioms and the theorems derived from them. All the bullshit and fluff I've seen in standard geometry textbooks is missing... for the reader's benefit.

Typically they're taught in some kind of basic intro course. I did a Graph Theory course basically designed to teach proof techniques.

Combinatorics is a good setting for this because it really relies on induction.