AirPush was one company that did (does?) sell ads as Android push notifications. On the whole, they're really not that widely used anymore, though - partly because Android users pushed back hard against them about a year ago, IIRC, but also because the newest version or two of Android makes it really easy to identify the offending app and disable the notifications.

If I remember correctly, the pushback was before the new notification tray, so it may have been Android's own response to the problem.