I have only had this happen twice, and it has annoyed me to no end until I figured out what was causing it. What I am talking about are two different issues caused by the same piece of adware; one issue is a weird icon appearing in your Android notification area. Another is an icon just showing up out of the blue on your main Android home screen. What causes this is an app called Airpush.
Airpush is an evil adware app that does this to help fund application developers. Airpush is not an app in and of itself, but can be included in some applications you install on Android. To see what I am talking about, check out this article on PCworld.
What app is doing this? Use Airpush Detector.
Airpush Detector is a handy application that can be used to find the offending app or apps. Just install this app and it will reveal which apps you need to get rid of. Once I find the app and get rid of it, I usually will send it a bad review as well.
There is an opt-out on the web that you can use to avoid these ads, but no way that you would know you could even do this. They also have an app for opting out, but I would not install ANYTHING from them on my phone as it would be suspect.
I am all for application developers making money, but making my phone do weird things shouldn’t be part of that equation.