The normal way to start an Application or Service is to implement a Broadcast Receiver that listens for the "boot completed" broadcast. This approach will only work for Applications that are not installed on the SD card, because "boot completed" is broadcasted before the SD card is mounted, therefore the Application can never receive the broadcast, see also: http://developer.android.com/guide/appendix/install-location.html#ShouldNot. But it is generally a bad idea to force the installation on internal phone memory as it is restricted. It is more likely for a user to keep an Application installed if it uses as little as possible internal memory.
There is an alternative that can be used in many cases. The USER_PRESENT intent is broadcast when a user is present after the device wakes up, e.g. the user unlocks the screen. With this intent it is possible to start a service that is installed on the SD card.