If tightening the bolts on the toilet doesn't work, you may have a cracked flange underneath the toilet. You don't mention how much it moves but if it's a lot, I would recommend pulling up the toilet (make sure to plug the sewer hole with a towel!) and making sure everything still looks okay underneath, including the flange and wax seal. A badly rocking toilet can lead to a leaky wax seal. If nothing is broken try to determine if the floor is just sloped or something that can be fixed with a shim or something to level out the floor.
If the toilet isn't moving that much, you can slide a metal or plastic shim underneath from the outside.
Just be aware that a lot of plumbers consider a rocking toilet to be a precursor to a leaking toilet so if it's been rocking for awhile you might want to take a look underneath just to be safe.