They’re totally, utterly useless.
Google “auto cool test” and you can see for yourself; it seems like every local network affiliate west of the Mississippi has done a report on them, and the results are universally negative.
Here’s an example:
http://www.wnep.com/Global/story.asp?S=5151765
Key phrase being “when you get off work.” You’ll see clusters of cars actually under the trees and in the morning shade, but only the clever folks park in a space where the sun is shining now, but will be in the shade later. If you leave late enough, you don’t have to park under the tree itself, so you can avoid some of the bird droppings.
If you can’t park in shade, the sun shade under the windshield has an advantage that nobody’s mentioned (unless I missed it). Your A/C ducts probably run under the dash, so they get superheated in the sun, too. The absolute last thing I do before driving off is remove the sun shade. Then sometimes I’ll even drive the car to a spot (if there is one) where I can let it stand in the shade until the A/C catches up.
Oh yeah, if your car has a big rear windshield, you might consider parking nose out rather than nose in, if that gets your (shaded) front windshield facing the sun more at the right time of day.
Has anybody mentioned drinking lots of fluids before you head out to the car? Not so much for cooling the car, but to survive the heat.