In my Application I am not having any UI part, so I need to start a Service as soon as the Applicaton gets installed on the Device. I saw many links from which the answer was that its not possible but I guess it is surely possible. Just have a look at PlanB Application on the Android Market that does fulfil my requirement. Below is my Manifest file how I tried, but the Service was not called at all. So, let me know what is the best possible way to start a Service when the Application gets Installed.

UPDATE

I also tried using android.intent.action.PACKAGE_ADDED it works fine for detecting the Package for the other Applications but not for itself.

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.auto.start"
    android:versionCode="1"
    android:versionName="1.0" >

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

    <application
        android:icon="@drawable/ic_launcher" >

        <service android:name=".MyService">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </service>

        <receiver android:name=".BootUpReceiver">
            <intent-filter>
                <action android:name="android.intent.action.BOOT_COMPLETED"/>
                <category android:name="android.intent.category.DEFAULT"/>
                <action android:name="android.intent.action.PACKAGE_INSTALL" />
                <action android:name="android.intent.action.PACKAGE_ADDED" />
                <data android:scheme="package"/>
            </intent-filter>
        </receiver>
    </application>
</manifest>

Fortunately, Plan B does not work on Android 3.1+, as tested on a XOOM and a Galaxy Nexus.

What Plan B does is exploit a security hole that could be used by drive-by malware, which is specifically why Android prevents it from happening anymore.

---

UPDATE

To clarify: As inazaruk posted and I put into comments on other answers, all applications, upon installation, are placed in a "stopped" state. This is the same state that the application winds up in after the user force-stops the app from the Settings application. While in this "stopped" state, the application will not run for any reason, except by a manual launch of an activity. Notably, no BroadcastReceviers will be invoked, regardless of the event for which they have registered, until the user runs the app manually.

This block covers the Plan B scenario of remote-install-and-run, which they were taking advantage of previously. After all, with that, anyone with a hacked Google account would be at risk of having their device infected, hands-free as it were.

So, when the OP says:

I need to start a Service as soon as the Applicaton gets installed on the Device

the OP will be unsuccessful and will need to redesign the application to avoid this purported "need".

I am having a Simple AutoStart Application with TimerTask implementation, that works fine in almost many devices. The problem is that it is not working in Samsung Galaxy Y(2.3.6) and DELL XCD35(2.2). When the device boots TimerTask works for some seconds and then shuts down. I check in the Application->Manage Application, I saw that the Applcation was already in Force Stop State. That means some how my Application gets stopped after some seconds. So, what is the reason for this weird behaviour in these two devices, if anyone has the solution do share it.

Below is my code.

MyReceiver.java

public class MyReceiver extends BroadcastReceiver{

    private Timer mTimer = new Timer();
    @Override
    public void onReceive(Context context, Intent arg1) {
        Toast.makeText(context, "Device Booted", Toast.LENGTH_LONG).show();
        Log.d("TAG","Device Booted");
        mTimer.scheduleAtFixedRate(new MyTimerTask(), 2000,2000);
    }

    private class MyTimerTask extends TimerTask
    {
        @Override
        public void run() {
            Log.d("TAG","TimerTask executed....");
        }
    }
}

AndroidManifest.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.autostart.app"
    android:versionCode="1"
    android:versionName="1.0" >

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

    <application
        android:icon="@drawable/ic_launcher"
        android:label="@string/app_name" >
        <receiver android:name=".MyReceiver">
            <intent-filter>
                <action android:name="android.intent.action.BOOT_COMPLETED"/>
            </intent-filter>
        </receiver>
    </application>
</manifest>

I think in some of the Android OS sometimes the OS kills the threads that are running while the Devices Boots which Android is not familiar with or doesn't recognize it. This is the reason why the TimerTask is working in some Devices and in some Devices just works for a 5-10 seconds and then the Application is ForceStopped automatically by the Android OS on Device Boot(Note - Its Force Stop from Manage Application and not Force close so I am not getting any error in the Logcat).

So in that case the solution is to use the inbuilt Mechanism which Android OS recognizes and doesn't kill it and keeps it in a running mode. In this case I managed using AlarmManager to perform my task and it works.

I might not be right but my final solution was to use AlarmManager to make my Application working in every Device.

@Override
    public void onReceive(Context context, Intent arg1) {

        Log.v("Device Booted", "************ DEVICE BOOTED ******************");
        Intent myIntent = new Intent(context, AlarmService.class);
        PendingIntent pendingIntent = PendingIntent.getService(context, 0, myIntent, 0);
        AlarmManager alarmManager = (AlarmManager) context.getSystemService(Context.ALARM_SERVICE);
        alarmManager.setRepeating(AlarmManager.RTC_WAKEUP, System.currentTimeMillis() + 2000, 2000, pendingIntent);
    }