It uses many kinds of sensors. Yes I know about clutter, I've spent quite a lot of time in the radar industry. But by combining data from radars of multiple wavelengths, it becomes pretty feasible. Though yes, difficult.
We need to fundamentally redesign our road systems to accommodate self driving cars. That might happen... in 50-100 years...after we address the already crumbling infrastructure we have. For perfect, sunny conditions, like the roads in Nevada all these self driving startups are doing their testing, with straight flat landscapes, I am sure the tech can work fine. Rest of the country, maybe not so much.
Radar clutter, attenuation, penetration, etc are all affected by wavelengths. By using multiple frequencies, you can get a better idea of what is and isn't really there. As far as interference, there are ways to filter out noise. The car presumably knows how fast it is going. Therefor, it can do doppler filtering on the received waves. IE... car knows it sent waves at 50 GHz and is traveling at 60 mph. It knows to expect a response at ~54 GHz from the front and 50 GHz from the side.
For tracking objects, you can use a pulse-doppler radar [0] to get both range and rate information.