For those who like videos, I would highly recommend utilizing Andrew Ng's Coursera ML videos for step one. I found his lectures to be good high level overviews of those topics.
The course in general lacks rigor, but I thought it was a very good first step.
Andrew Ng's Coursera course is probably good for some backgrounds. But if your background is as someone who has mostly been programming for the last few years, I feel that Andrew Ng's course has two big drawbacks:
1. It's not very hands-on or practical. You won't actually get the feeling of building anything for a while.
2. It's very math oriented. If the last time you took a math class for your CS degree was a few years ago, you run the risk of not really remembering the background material well.
I'd personally recommend doing two things in parallel, if your background is in programming with less math training:
1. Look for a very hands-on/practical course to try out some examples.
2. At the same time, start refreshing (or learning) some maths that you might not remember, specifically, probability and statistics. Then after, Linear Algebra and maybe calculus.
I'm going to disagree with this about the difficulty of the math in Andrew Ng's course. Do you remember how to differentiate a function? Look up partial derivatives if you don't remember how they work, it shouldn't take longer than an hour. You're probably going to be fine.
If you never took calculus it's probably going to be hard going, but almost all modern machine learning requires basic calculus.
I would really recommend going through the first part of the course about linear regression if you haven't encountered it before, it was really eye opening for me.
Linear regression is incredibly important, but I think it's much better understood either practically (by implementing it or using it), or if you want to understand it mathematically, at the "end" of a statistics course. There's a reason that when learning probability/statistics, you usually encounter Linear Regression near the end of an introductory course, not in the beginning.
Again, this really depends on how mathematically competent you already are. I'm just basing this on how I felt coming to the course after having finished my degree about 10 years ago, therefore not really having most prob/statistics fresh in my mind.
You can certainly complicate the hell out of linear regression, but Andrew Ng introduces it in the setting of optimization/stochastic gradient descent, which I think is both mind blowing and a much simpler introduction than most statistics courses.
It's the very first bit of the course, I think everyone who is interested should try learning it. If not it's fine, but I wouldn't want anyone to not even try to spend a few hours on it because someone on the internet said it would be too hard.
That's certainly reasonable. And I totally agree with "try it out and gauge for yourself whether it's valuable for you".
My worry is that people will be put off from the field of machine learning if, 3 lessons into Andrew Ng's course, they will see that they don't understand anything, and that it's not practical to boot.
So my advice (generally applicable) is to try a few different things, because different resources click for different people.
The course in general lacks rigor, but I thought it was a very good first step.