1. Give ample warning. The time frame depends on what your product is and how difficult to replace it is, but I'd consider anything less than 1 month for a consumer product or 3 months for a business product to be unacceptable unless you're on the verge of bankruptcy or something.
2. Consider grandfathering in existing users. This doesn't need to be free forever, but X months free goes a long way towards keeping people happy. This can be combined with the previous point; for example, you could announce that new users will be paid only either immediately or starting soon, while existing users have X months free after which they will need to pay.
3. If applicable, give your users a way to export their data from your service before it goes paid. Even if most of them won't use it, it helps avoid feelings of lock-in or bait-and-switch.
4. General considerations for paid services: consider a free tier or free trial. Free tiers can be very effective when most users don't use many resources. It may or may not be appropriate for your case.