A service is an object that provides functionality to other components in a loosely coupled way through an interface and is often a singleton.
This is a fitting definition, but doesn't indicate belongs in a service or when something should be service. Services reside outside the View-ViewModel pattern and provide functionality to anything that needs it. In practice a service should address an area of business logic and have an appropriate name which describes the functionality it contains, like CustomerService or DataService, etc.
Avoid making a service a dumping ground for functionality you don't know where to put. I tend to view services as static libraries of functionality, generally consisting of methods (think WCF Service Contracts). My personal preference is to avoid storing state or exposing properties in services. I don't use services to control workflow. Instead I would implement a Controller to govern the workflow, and have the Controller consume the service.
On one Prism project, we would have regular design meetings where we would discuss where a given piece of functionality should reside. The governing rule that came about, was that the ViewModel is directly concerned with the View and servicing the View; code that belongs in the ViewModel is there because of some requirement dictated by the View. If that wasn't the case, we were probably looking at a general piece of business logic which likely belonged in a service (or Controller, if one existed).
Following this line of thinking, we found more and more of our code moving to services, until we had a robust services layer, and a lean ViewModel which simply became a consumer of the services. This approach prevented business logic getting lost or hidden in ViewModels. It also supported our decision to separate out our services into their own assemblies, which I would highly recommend.