以下のようにBroadcastReceiverを実装する。

public class BootBroadcastReceiver extends BroadcastReceiver {
    @Override
    public void onReceive(Context context, Intent intent) {
        if (
                (intent.getAction().equals(Intent.ACTION_PACKAGE_REPLACED) && intent.getDataString().contains("com.my.app")) ||
                intent.getAction().equals(Intent.ACTION_BOOT_COMPLETED)
        ) {
            Intent i = new Intent(context, NotificationService.class);
            context.startService(i);
        }
    }
}

Manifestファイルに以下の記述を付加してBroadcastIntentを受け取れるようにする。

        <receiver android:name=".BootBroadcastReceiver" android:permission="android.permission.RECEIVE_BOOT_COMPLETED">
            <intent-filter>
                <action android:name="android.intent.action.BOOT_COMPLETED" />
                <category android:name="android.intent.category.DEFAULT" />
            </intent-filter>
            <intent-filter>
                <action android:name="android.intent.action.PACKAGE_REPLACED" />
                <data android:scheme="package" android:path="com.my.app" />
            </intent-filter>
        </receiver>

permissionを忘れずに付加する。

    <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />

permissionを書き忘れると、Android3.1以降の端末で上手く検知できなくなる。また、SDカードにインストールしている場合は、Intentを受け取れないのでSDカードがマウントされた時にフックする必要がある。