This depends a lot on the size of your project, and what exactly you are implementing. I've found that a lot of formal documents are overkill for most small projects. I usually start by writing myself a list of things that need to happen before I implement. I ask myself questions like:
- What actually will be implemented?
- When do we want to do it, and what do we need to check before we do the implementation?
- Do users have to be out of the systems when we do the implementation?
- Is there a time-dependency (i.e. outside business hours, on the weekend, etc) for our implementation?
- How many actual servers/workstations/databases are going to be updated?
- Is this a brand-new application, or an upgrade to an existing system (the answer to this changes your implementation plan A LOT)?
- What are the actual steps we will take to do the implementation?
- How will we back up the existing system before we implement, in case we need to roll back?
- How will we test the application after it is implemented?
- How do we roll back to our backup?
- Who needs to be notified about the implementation (before, during, after, statuses, etc.)?
- Do we have documentation of what the changes are, and how the users can use the new changes?
- Who's going to take support phone calls from users?
Once I have answers to these kinds of questions, I write up the plan, usually as a basic Word document, with different sections and a timeline. I like to put in the detailed step by step parts, with paths to files, etc., logins, etc., so I will have all the sticky little detail in one place.
As a morning person who has to do installs when I'm normally sleeping, I like the comfort of a list of all the steps I need to take, so I don't forget something. I think it is worth writing down the communication steps you'll take, particularly if a group is doing the implementation, and some items are dependent on the others, or if you aren't all in the same place. (ex. I will email Fred when the database updates are complete, so that he can do the web server updates, Fred will email us all when he's done, so we can all do the testing)
Then, once you have one that works, it can become your template for future updates to the same system, or be a jumping off point.