First be sure to read: http://developer.android.com/guide/components/processes-and-threads.html#Lifecycle
The key to this is that on Android a process is just a container for code — or specifically one or more components (activities, services, receivers, providers). By default all components in a .apk get their own, dedicated process, that they all run in together. This is almost always what you want.
When the user is directly interacting with a component of that process (that is an activity) Android will try very hard to keep that process running, and you won’t see it killed except under extraordinary circumstances.
When the user is no longer directly interacting with the process, then it becomes expendable relative to other processes as described in the referenced documentation. That is, empty processes (no interesting components) will be killed before processes holding activities that the user had been using, which will be killed before processes with running services. So having a running service will tend to keep your process around at the expense of other processes.
At the same time, we need to deal well with more and more applications leaving services running, often indefinitely, and often with memory leaks. So has a service runs for an increasingly long time, Android will try less and less hard to keep its process going. Effectively this means moving it down to the background bucket until the out of memory killer takes it out. After that, if the service still wants to run, then a new process will be created for it to be restarted in.
The upshot is that for normal services that are running a long time, it is expected behavior that their process will get killed after a while. This doesn’t need to stop the service; a service that wants to continue running will do so, it will just need to be instantiated in a new process.
Of course as long as the user is interacting with an activity in your process, the process won’t be killed, since this pulls it to the foreground category regardless of what is going on with any services in it.