What is the proper procedure for replacing rusted toilet anchor bolts?
The anchor bolts almost surely attach through the toilet flange.  This diagram shows the general layout.  (Click here for more detail.)



That image is part of U.S. Patent 7069603 showing who-knows-what.  Here is what the flange and closet fitting have looked like in new construction for the last 20 years or so:



(photo uploaded by user "molo" and posted here.)

The six small holes are for fastening the flange to the flooring and indirectly to the subfloor.  The two enlongated circular slots are for the heads of the bolts to slip under to fasten down the toilet.  Shown with a new wax ring they should look like this:

 (posted by "adams444" here.)

Replacing these are simple in theory.  


Buy a wax ring which are about $3.  Buying two would not be overkill (see details further down for why).  There are also kits with replacement anchor bolts for about that much again.
Give the toilet a few flushes to make the whole experience a little more pleasant.
Turn off the water.
Flush again and hold the handle to get as much water out of the tank as possible.  Use a plunger to get most of the water out of the bowl.
Disconnect the water line from either under the tank or from the valve coupling.
If it is a two piece toilet, is heavy, and you don't have a helper, look inside the tank for a way to detach the tank from the base.  Be prepared for a half gallon of water to splash out by having a bucket, towels, mop, etc. on hand.  Otherwise prepare to lift the toilet as a single unit.
Remove the nuts from the anchor bolts.
Lift toilet mostly straight up.  You may have to rock it side to side or front to back to overcome the wax ring's adhesion while lifting.  To minimize water splashing on the floor, keep it tipped forward (away from the wall) and set it out of the way.
Assess the situation.  Maybe you want to replace the flange, or even install one if the installation is really old.  Most hardware stores sell kits with a flange, bolts, nuts, and wax ring for about $6.  You'll have to make sure the pipe underneath is compatible with the new flange:  if it is recent construction (~1980s and later), some ABS glue will be needed.  If it is older, an ABS to cast iron coupling is needed (and maybe some pipe sawing).
Note that a modern flange is designed to go on top of the flooring which is meant to go all the way under the toilet.
Once the flange is good to go&mdash;be sure it is installed in the proper orientation so that the anchor bolts can go in the curved slots and through the toilet&mdash;measure how much bolt length is actually needed and break or cut them to length, install them, the wax ring, and set the toilet into position.  To do this smoothly without experience, use two helpers:  two to lift and position the toilet and one eyes on ground positioning the anchor bolts (they tend to tilt) and directing the other two.
Put the anchor nuts on, moderately tighten, and check if the toilet is loose.  If the bolts are still too long, you might be able to hacksaw them with the toilet in position (put nuts on first so they can de-burr the thread at the cut).  Otherwise, if you lift the toilet out again, it is best to install another new wax ring.  (The squished new one makes a great shop item for waxing nails and screws for easier assembly.)
Reassemble and reconnect water line.


With everything ready to go, this is 60&ndash;90 minutes work.  If everything goes wrong, it could take half a day.

The biggest danger is that once the toilet is off, you will see sub-floor (and maybe a floor joist) with dry rot and worse.  Then you'll have to choose whether to just fix it up as best you can, or tear the floor up and replace everything that is wrong.

Good luck!