You could easily do something like this by:
- Have you app set an alarm using AlarmManager
- Have the receiver for the alarm start a Service that checks for updates
- Display the notification to the user using the NotificationManager
That is a polling solution, which should be fine and probably better in most circumstances like you described.
However, if you want a push solution, you can look into Android C2DM which allows your server to send push notifications to a registered Android device.
Edit
How do apps run 'without being launched'?
Well there's a few ways. One is that any app can register for different device events; one of those is a boot-complete event.
The second way is using the AlarmManager. If an app has set an alarm then the user navigates away from the app and then the OS decides to close the app, the alarm can still be registered to run at a certain time. When this alarm is triggered will run whatever code the app developer likes, including starting a Service. Of course doing this without notifying the user can be an issue, especially if the service drains battery, etc.