One of the key features of Android is the ability for apps to provide notifications that pop up in the status bar. I'll try to explain in this post how you should implement a Service component that polls a web service regularly to check for updates.
The first thing you need is a preferences activity, where the user can set what notifications they want and how often they want your app to check