Androidでは、端末の起動時に発行されるandroid.intent.action.BOOT_COMPLETEDというブロードキャストインテントを受け取り、処理を実行させることができます。

これを利用し、バックグラウンドで常駐するアプリを作成することが可能です。
ここでは例として位置情報を取得し、位置情報が更新されたらトーストでメッセージを表示するサービスをバックグラウンドで常駐させるように作成しています。

AndroidManifest.xmlのapplicationタグ内に以下を記述

<service android:name="ExampleService"></service>
<receiver
    android:name=".BootReceiver"
    android:enabled="true">

    <intent-filter>
        <action android:name="android.intent.action.BOOT_COMPLETED" />
        <category android:name="android.intent.category.DEFAULT" />
    </intent-filter>
</receiver>

起動時にブロードキャストインテントを受け取れるようにパーミッションの設定を記述します。

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

ブロードキャストインテントを受け取るブロードキャストレシーバーを作成します。
onReceiveにて、常駐させたいサービスを起動させます。
BootReceiver.java

import android.content.BroadcastReceiver;
import android.content.Context;
import android.content.Intent;
import android.widget.Toast;

public class BootReceiver extends BroadcastReceiver {

    @Override
    public void onReceive(Context context, Intent intent) {
        String action = intent.getAction();
        if (action.equals(Intent.ACTION_BOOT_COMPLETED)) {
            Toast.makeText(context, "BOOT_COMPLETED", Toast.LENGTH_LONG).show();
            context.startService(new Intent(context, ExampleService.class));
        }
    }

}

実際に常駐するサービスを作成します。
ExampleService.java

import android.app.Service;
import android.content.Intent;
import android.location.Location;
import android.location.LocationListener;
import android.location.LocationManager;
import android.os.Bundle;
import android.os.IBinder;
import android.util.Log;
import android.widget.Toast;

public class ExampleService extends Service implements LocationListener {

    static final String TAG = "ExampleService";
    private LocationManager mLocationManager;

    @Override
    public void onCreate() {
        Toast.makeText(this, "バックグラウンドサービスを開始しました。", Toast.LENGTH_SHORT).show();
        mLocationManager = (LocationManager) getSystemService(LOCATION_SERVICE);
    }

    @Override
    public int onStartCommand(Intent intent, int flags, int startId) {
        Log.i(TAG, "onStartCommand Received start id " + startId + ": " + intent);
        mLocationManager.requestLocationUpdates(LocationManager.GPS_PROVIDER, 1000, 0, this);
        //明示的にサービスの起動、停止が決められる場合の返り値
        return START_STICKY;
    }
 
    @Override
    public void onDestroy() {
        Log.i(TAG, "onDestroy");
          mLocationManager.removeUpdates(this);
    }

    @Override
    public IBinder onBind(Intent intent) {
        return null;
    }

    @Override
    public void onLocationChanged(Location location) {
        Toast.makeText(this, "位置情報を更新", Toast.LENGTH_LONG).show();
    }

    @Override
    public void onProviderDisabled(String provider) {
        
    }

    @Override
    public void onProviderEnabled(String provider) {
    }

    @Override
    public void onStatusChanged(String provider, int status, Bundle extras) {
    }

}

作成したアプリをインストールし、一度再起動した端末にて、
[設定]-[アプリケーション]-[実行中のサービス]で作成したアプリのところを確認します。
「1件のプロセスと1件のサービス」と表示されていれば成功です。
位置情報が更新された時に、正常にメッセージが表示されるか確認しましょう。