Build the Statement of Work (SOW)
To some extent, you've probably developed the majority of the content for the Statement of Work. The process of decomposing implementations, estimates, and calculating risk has probably generated a decent amount of documentation between you, the developers, and the customer. It's time to organize that documentation into a draft Statement of Work. A good statement of work will define assumptions, clarify features, define milestones (and ideally the tests of completion). Of course, the customer will have details that are important to them as well. If scope changes during this process, make sure you go back and update the ROM estimate.
One particular tip that I think is really helpful, if you haven't done so already, it to define as many functional inputs and output specifications as possible. To us, that usually means GUI wireframes, APIs, and network protocols; today you may also want to define gestures, voice, etc. You can't define application implementations until you can understand and describe the inputs and outputs of the application.
It's also important to agree on quality. If possible, find work samples that reflect the quality bar you expect to achieve. Setting expectations is paramount and setting quality expectations is one of the more difficult tasks to accomplish since quality is not nearly as quantitative as other more technical specifications.
Determine Final Quote & Final Statement of Work
You are almost there. The last step will generate the final version of documentation required to perform a waterfall project correctly. You've answered what (SOW) and how much (ROM Estimate) but you still haven't modeled all of the complexity to answer when. And in order to do that, you need to have your final answer of the last "W" which is who.
For the final answer, we use Microsoft Project. Many people cringe when I mention Microsoft Project, but once you learn how to use it correctly for software projects, it's quite useful. The key is to add the "work" column (Right click on the header and select "Insert Column") and enter your estimates there. Don't enter work under the duration column; it will drive you crazy if you start using more than one resource to complete a task.
Finally, if you find yourself using dependencies to keep things from going crazy you have done something wrong. Dependences should only be used to represent a real work dependency -- not as a tool to force project into submission. If you want a task to begin or end sooner, use priority. If you want a set of work, like a milestone, to begin after another set of work, like the next milestone, then use dependencies at the milestone level. Add resources and use leveling liberally. If you aren't hitting "level resources" a lot, you've done something wrong and Project will be more difficult to use than it should. The strong majority of people that dislike Project probably aren't using it correctly.
With everything in project, you now have a reasonably accurate set of dates to share with your customer. By filling out the resource section, you also have a clear understanding of who will do the work.
Start the SOW with the customer's high-level goals. If you project no longer meets those goals... something went wrong along the way.
You have finally answered What, How, When, Who, and How Much. You've accounted for risk, which is the area most project managers fail to consider when building estimates. Those elements are everything you need to perform a FFP contract. Moving forward, if you prefer to run your team in an agile format, you can take your tasks in project and move them into the Agile project management system of your choice. At GarageGames, we use Jira and GreenHopper. I prefer to use Microsoft Project as my backlog and enter tasks during sprint building time while others at GarageGames like to enter the tasks from project directly into Jira.
Now to the final point: In the beginning of the document I mentioned that I thought it wasn't possible to make something truly waterfall. And what I meant was that all software projects require some flexibility. You may need to make changes on the fly. Discuss with your customer if there is wiggle room in dates or features in cases where things are slipping. It's not realistic to thing that nothing will change, so be sure to leave some room for... well...agility.