When I do this, it's a multi step process. Typically, there's an existing product to keep running. Rewriting from scratch is rarely an option, even though you end doing it eventually.
- Begin to ditch manual include statements and implement an autoloader, where possible (takes many passes)
- Create a helper script to simulate magic quotes & register globals. This is so you can turn it off in PHP, while keeping the existing code running
- Gradually remove excessive strip_slashes or add_slashes calls, if applicable. The helper script allows you to do this per file.
- Ensure that your variables have proper scoping
- Separate out your presentation code. Consider Smarty or alternate template system
- Move the DB calls to PDO and use parameter substitution for everything
- Look at the code and think about stubbing out a front controller
I then look at the project and determine how I'm going to alter the logic itself. Often, if there are no functions at all, my first pass is to wrap common behaviors into static methods. Get as much reuse without too much effort, so I'm not concerned with organization yet.
After the redundancy is reduced, then I get to organization. It's at this phase that I start planning out my class models and refactoring the functions into clean methods. This is also the time for automated tests (phpunit). Once I'm reasonably confident, I add some controllers and integrate the templates, then I'm done... barring one or two more passes.
For me, it's all about identifying where I am, where I want to be, and making a plan that can be executed in several small steps. Everybody has their own objectives, so there's no magic plan to follow except your own.