So after a bit of research I decided to start working my way through "How to Prove It" by Velleman, which has introduced me to many of the concepts that seem to be pre-requisites for this course: set theory, logic, proof strategies, etc.
I was able to start at the beginning and get all the necessary math to actually step forward to some of the more complex courses. I'd suggest starting there.
To me they were most useful when I just needed a refresher on the precise operations to go through in order to solve a particular kind of problem, but already understood it. It's hard to beat a textbook for learning material that is completely new to me.
Looking back at the psets, i think it's actually worth looking at them in reverse order just to not get too discouraged: the class ends on some number theory and begins with the Relation/Axiom/Set/Sequence stuff you see in early high level math classes. Some of that number theory/counting stuff is incredibly accessible from the outset, so the class doesn't just get monotonically more obtuse.
That said, if you've worked through vellman and you finish up this class, you're more than ready to do a class in proper number theory, discrete math or even real or complex analysis. Somebody else said that this course was a prereq for clrs, it is sort of, but you could take them both concurrently if you had to, as clrs doesn't have such a strong focus on proofs (if you're interested, 6.045j is a good followup in automata/computability/etc, lots of regexes, state machines and turing machines)
anyhow, i just want to say that it's ok if you don't get it all at once. i think i ended up seeing lots of these ideas two or three times in a variety of classes. probably the first time i was just mechanically spitting out proofs without understanding them. by the third time i came across them, they actually clicked for me. But there was value (for me at least) to exposure early on because you do know the things that are hazy and it's easier to dive deeper on those the next time you encounter them.
have fun!