Listen for the ACTION_BOOT_COMPLETE and do what you need to from there. There is a code snippet here.
Update:
Original link on answer is down, so based on the comments, here it is linked code, because no one would ever miss the code when the links are down.
In AndroidManifest.xml (application-part):
<receiver android:enabled="true" android:name=".BootUpReceiver"
android:permission="android.permission.RECEIVE_BOOT_COMPLETED">
<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" />
...
public class BootUpReceiver extends BroadcastReceiver{
@Override
public void onReceive(Context context, Intent intent) {
Intent i = new Intent(context, MyActivity.class); //MyActivity can be anything which you want to start on bootup...
i.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK);
context.startActivity(i);
}
}