Unter Android kann man eine Anwendung automatisch nach dem Systemstart starten lassen. Ich weiss allerdings nicht wie (also so, wie es beispielsweise Antivirensoftware macht). Wie geht man dazu und welche Funktion kann oder muss ich dazu nutzen? Und ist es möglich den automatischen Programmstart an bestimmte Bedingungen zu knüpfen (z.B. es besteht eine Online-Verbindung)?

Das geht mit einem BroadcastReceiver, den du in deinem Manifest definieren musst.

Z.B. so:

<receiver android:name=".receiver.StartupReceiver" android:enabled="true">
            <intent-filter>
                <action android:name="android.intent.action.BOOT_COMPLETED"></action>
                <category android:name="android.intent.category.HOME">
                </category>
            </intent-filter>
</receiver>

Android meldet dann deinem so registrierten BroadcastReceiver namens "StartupReceiver" dass das Booten abgeschlossen ist.

Der Receiver könnte z.B. so aussehen:

public class StartupReceiver extends BroadcastReceiver {
    @Override
    public void onReceive(Context context, Intent intent) {

        if (!MyInternetHelper.isConnectedToInternet())
            return;

        //Falls der Receiver mehrere Intents bearbeiten kann, 
        //kann man hier die Intents unterscheiden
        //if (intent.getAction().equals(Intent.ACTION_BOOT_COMPLETED)) {
            // z.B. Service starten
            PushService.actionStart(context);
        //}
    }
}

Mit Hilfe des Contexts hast du dann eigentlich fast alle Möglichkeiten.
BroadcastReceiver laufen allerdings soweit ich mich erinnere auf dem Main Thread, es sollten also keine allzu langen Aufgaben im Receiver ausgeführt werden, oder halt an einen Service abgegeben werden, sonst kommt ein "Activity Not Responding"-Error.

Viel Erfolg!