I think I started out with just about the hardest DVD of all - Step Blast. I'd recorded it off of FitTV, so I didn't know any better and just went for it. I did a lot of rewinding before finally getting ALL the choreography, which took several months since it took me that long just to get through the whole workout (I was one of the 20-minute cardio session people before discovering Cathe, so my body had a lot of adjusting to do).
After learning that one, it seems like the rest are just EASY! I pick the steps right up after about 2 tries (or for especially intricate sections, I take out the arm work until I've got the leg work down pat). Previewing ALWAYS helps, too. I'll sit and watch the DVD and fast forward and pick up just the basics, then I'll get up and go for it.
It does get easier with time, because you get used to the moves and the names Cathe gives them. After a couple years, you'll look back when someone else asks this question and think to yourself how easy it is to pick up the steps once you get used to Cathe's workouts!