Dentro del método onCreate():

NotificationCompat.Builder mBuilder =
        new NotificationCompat.Builder(PrimerPaso.this)
        // Aquí el icono pequeñito que queremos mostrar
        .setSmallIcon(android.R.drawable.sym_action_chat)
        // Aquí el icono grande
        .setLargeIcon((((BitmapDrawable)getResources().getDrawable(R.mipmap.icono_grande)).getBitmap()))
        // El título de la notificación, aparece en la barra superior (status bar) junto con el icono pequeño
        .setTicker("Alerta Paellapp")
        // El título grande
        .setContentTitle("Ya ha finalizado el tiempo")
        // El texto para dar una instrucción al usuario        
        .setContentText("Corre, pulsa para pasar al siguiente paso.")
        // Si queremos pasarle un número de acciones que han sucedido.
        .setContentInfo("1");
       

//Con lo anterior ya estaría funcionando la notificación, el siguiente código es para que cuando el usuario haga clic sobre esta, la aplicación se ejecute donde nosotros queramos
Intent notIntent = new Intent(DondeEstamos.this, DondeQueremosIr.class);
//Si le queremos pasar parámetros añadimos la siguiente linea, y PendingIntent.FLAG_UPDATE_CURRENT dos lineas mas adelante, sino, donde va PendingIntent.FLAG_UPDATE_CURRENT ponemos "0"
notIntent.putExtra("parametro", variableParametro);
PendingIntent contIntent = PendingIntent.getActivity(DondeEstamos.this, 0, notIntent, PendingIntent.FLAG_UPDATE_CURRENT);
mBuilder.setContentIntent(contIntent);


NotificationManager mNotificacionManager = (NotificationManager) getSystemService(Context.NOTIFICATION_SERVICE);
// ID_DE_NOTIFICACION tiene que ser un ID único para cada notificación que lancemos, o le pasamos ID_DE_NOTIFICACION, o un número.
mNotificacionManager.notify(ID_DE_NOTIFICACION, mBuilder.build());

Más info en la maravillosa documentación de Android: http://developer.android.com/intl/es/guide/topics/ui/notifiers/notifications.html