I suggest that you use AlarmManager in connection with a SQL database to handle notifications. You could use AlarmManager to schedule alarms which are fetched from your database. You should use a BroadcastReceiver to add alarms when the phone boots in order to handle the situation where the phone is rebooted by the user or system failure.
This howto explains how to use the AlarmManager.