Once More:

These are the steps to replace the cord: 

1. Buy some new cord.
2. Open up the housing which holds the spring-loaded starter pulley. 
3. Remove the starter pulley (if necessary)
4. Remove the old cord 
5. Attach new cord to pulley, probably with a knot. 
6. Wind new cord two or three times around the pulley. 
7. Thread the cord through the hole in the metal pulley cover. 
8. Re-attach the pulley to the engine motor or clutch 
9. Fasten the metal cover. 
10. Give the new cord a few pulls to test the recoil. 
11. Reattach the little plastic "T" pull handle. 
12. Mow.

Detailed instructions (continued):

The end of the string then needs to be threaded through the hole in the pulley cover, on its way to the starter pull handle.

Replace the pulley and cover, and fasten it with the bolts. 

Test the pull cord recoil. You want to make sure that the pulley rotates freely and has enough recoil to pull the cord back into the housing. Pull it a few times. I was impressed by how much more force I was able to use when the little black pull handle is on the end of the cord.

If the recoil works, then put the gas tank back on.

The starter handle was designed to sit at a convenient height on the mower handle. Ideally, the recoil spring keeps it ever-so-slightly drawn in towards the engine, so that the starter handle doesn't hang limply.

On the mower I was fixing, A long metal staple held the handle on the string. I used a chisel to pry the staple out of the old, broken cord. 

I pulled the cord tight, and held it where I believed the handle would sit at a convenient height. A small metal loop was mounted on the mower handlebar. I threaded the starter cord through this too.

I threaded the new cord into the handle and squeezed the staple into the new cord.

Repair complete! You should now be able to utilize the rewind starter on your mower. Actually starting the thing will be another challenge altogether. 

My mower advertised "One Pull Start" which was technically true, it just ignored the 34 pulls before that one.