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.