Usando Intent Services

AndroidManifest.xml

<!-- Não esquecer de declarar no Manifesto--->

    <uses-permission android:name="android.permission.INTERNET" />
    <uses-permission android:name="android.permission.VIBRATE" />
    <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />
    <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE"/>
    ...
    
 
 <service android:name="CatalogoService" ></service>

CatalogoService.java

package com.coderockr.testeandroid.jacksonfdam;

import android.app.IntentService;
import android.app.Notification;
import android.app.NotificationManager;
import android.app.PendingIntent;
import android.content.Context;
import android.content.Intent;
import android.support.v4.app.NotificationCompat;

public class CatalogoService extends IntentService {
	public CatalogoService() {
		super("CatalogoService");
	}

	@Override
	protected void onHandleIntent(Intent intent) {
		try {
			Thread.sleep(intent.getIntExtra("SLEEP", 10000));
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		NotificationCompat.Builder builder = new NotificationCompat.Builder(
				getApplicationContext());
		builder.setSmallIcon(R.drawable.ic_launcher);
		builder.setAutoCancel(true);
		builder.setDefaults(builder.getNotification().defaults
				| Notification.DEFAULT_SOUND | Notification.DEFAULT_VIBRATE);
		builder.setLights(0xFF0000FF, 500, 1000);
		builder.setContentTitle("Catalogo");
		builder.setContentText("Texto da notificação");
		builder.setTicker("Voce tem uma nova atualizacao");

		Intent activity = new Intent(this, productListActivity.class);
		PendingIntent launchIntent = PendingIntent.getActivity(this, 0,
				activity, 0);

		builder.setContentIntent(launchIntent);

		NotificationManager manager = (NotificationManager) getSystemService(Context.NOTIFICATION_SERVICE);
		manager.notify(0, builder.getNotification());
	}

}