[westoncb]

I was in a very similar situation. The thing that helped me the most was getting an understanding of what it is mathematicians are trying to do and what their methods are. "What is Mathematics?" ended up being pretty pivotal (as another poster mentioned), though the topics did seem pretty random to me when going through it at first. The introductory material to "The Princeton Companion to Mathematics" is an excellent compass for orienting yourself. That introductory portion is about 120 pages, though it's a huge book (well over 1000 pages) and the rest of it probably won't be too useful to you for a while (but at the same time, those intro essays were invaluable). I'd second Axler's "Linear Algebra Done Right" as a nice early (yet pretty serious, despite the title) book. Linear algebra is used all over the place, and the way it's addressed in that book you'll learn something about creating mathematical systems rather than merely how to use some existing system. It also helped me understand what's interesting and why in mathematics to read in philosophy of mathematics and math history, and popularizations, etc. "Men of Mathematics" is quite good, as are "Gödel's Proof" and "Mathematics and the Imagination."

Once I was immersed in it for a while, I started getting into more CS related mathematics: things in computation theory, programming language theory, category theory--and I would spend a lot of time reading networks of wikipedia math articles from basically random starting points inspired by something I read. Didn't understand much to start with, but I'm glad I did it and I find them indispensable now.

I think it's of the utmost importance to go into it with an understanding that you SHOULD feel lost and confused for quite a while--but trust in your mind to sort it out with a little persistence, and things will start coming together. If you find yourself avoiding math, finding it unpleasant and something you 'just can't do,' check out Carol Dweck's 'Self-Theories.' Good luck!