We only had 1 person out of the 4 graduating from our fellowship this year who needed a job. The other 3 all were doing subspecialty fellowships. This person was told by a physician recruiter that this year was the worst he had seen in 15 years. However, this fellow ended up getting a job locally with one of the large HMO's, and I believe had at least one other offer (was out of state but in a major metro area that he liked). Overall, I think people may have had to work a bit harder to get interviews, etc., but I don't think there is an oversupply of cardiologists. I guess some of it must depend on which area of the country you are in, and of course there is always more competition for jobs in big cities like Chicago, LA, etc.
How hard it is to get an interventional fellowship probably depends a lot on which fellowship you are in and how well connected the faculty are, and how good the cath lab/interventional training is perceived to be at your program. I don't really know, but I'm guessing that doing research/publishing in the interventional area(s) would be helpful too. Nobody from our program who wanted interventional in recent years has been unable to get a spot, although some had to go to other programs as we only have 1 or 2 spots per year.