How to show notification from background service?

First you need to read this article on how to use Notifications.

Next use this to send a Notification, you can write this code in the service class at the point where you receive some data from the client.

NotificationManager notificationManager =
    (NotificationManager) getSystemService(NOTIFICATION_SERVICE);
int icon = R.drawable.notification_icon;
CharSequence notiText = "Your notification from the service";
long meow = System.currentTimeMillis();

Notification notification = new Notification(icon, notiText, meow);

Context context = getApplicationContext();
CharSequence contentTitle = "Your notification";
CharSequence contentText = "Some data has arrived!";
Intent notificationIntent = new Intent(this, YourActivityThatYouWantToLaunch.class);
PendingIntent contentIntent = PendingIntent.getActivity(this, 0, notificationIntent, 0);

notification.setLatestEventInfo(context, contentTitle, contentText, contentIntent);

int SERVER_DATA_RECEIVED = 1;
notificationManager.notify(SERVER_DATA_RECEIVED, notification);

Am I reading this incorrectly? Both your server app and your client app are both on the same Android device?

In any case, take a look at the ApiDemos for code for notifications through a service.

And since you're probably going to be dealing with a remote server (and not a local one) and all the latency issues associated with the network, I think you better wrap your service in an AsyncTask.

Also learn about Broadcast Receivers, registered Broadcast Receivers can be great way to trigger Services/Activities without the need to have your own Service polling in a loop indefinitely.