Is this red star icon malware? How to get rid of it?
Definitely looks like a case of AirPush. This is a particularly invasive form of in-app advertising that uses the notification bar, even if the app utilizing it is not actively running.  Technicaly it's not malware but adware, although the way it manifests itself certainly blurs the line between the two.  The only way to stop these ads from appearing in your notification bar is to uninstall the application that came bundled with AirPush.

There are several apps on the Market that can help you detect which app uses the AirPush, so that you can uninstall them.

[Edit]
Apparently AirPush gave in to the public outcry and are now providing ways to opt out of their invasive ads: http://www.airpush.com/optout  You can either download their "opt-out" app, or manually enter your device's unique IMEI/ESN/MEID on their site.  Personally, I'd still uninstall the bundled app, since both opt-out methods would most likely use bandwidth for connecting to AirPush servers to authenticate against their databases.