環境
AndroidStudio 2.0

Android Support v4 23.3.0

AppLaunchChecker
http://developer.android.com/intl/ja/reference/android/support/v4/app/AppLaunchChecker.html

MainActivity.java

    @Override
    public void onCreate(final Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);

        boolean before = AppLaunchChecker.hasStartedFromLauncher(getApplicationContext())
        AppLaunchChecker.onActivityCreate(this);
        boolean after = AppLaunchChecker.hasStartedFromLauncher(getApplicationContext())
    }

AppLaunchChecker.onActivityCreate(this); によって計測が行われている

アプリケーションを新規インストール後にMainAcvitity起動
before: false
after: true

アプリケーションがタスクにいない状態から起動
before: true
after: true

アプリケーションのデータ削除後に、アプリを起動
before: false
after: true

AppLaunchChecker.onActivityCreate(Activity) が呼ばれるまでは常に
AppLaunchChecker.hasStartedFromLauncherは false、逆に一度でも呼んでしまうとアプリがアンインストール（もしくはデータ削除）されない限りは true であり続ける

SharedPreferencesなどを用いて同様のロジックを組めるが、こちらの方が手軽。ただし、あとから追加というのが出来ないのでどのバージョンでも「新規インストール時」に処理を行いたい場合という限定的な仕様用とになりそう