Here's a great tutorial that explains the entire process:
http://www.antiqueradio.org/recap.htm
I'm in the process of doing the exact same thing with an amp of mine, and decided to use terminal strips below the chassis. I've removed the multisections (after taking photos and making very clear notes for reattaching all the wires) and cleaned their terminals - I'll reinstall the multisections in order to use their ground points- that is, where they attach to the chassis - for the new capacitors. From what I understand, this should eliminate the introduction of any new ground loops (60 Hz hums), as well as maintaining the original look of the amp.
Some components' leads were a bit short for connecting to the terminal strip, so I'm now awaiting some new cloth covered wires to complete the project.
Regarding your question about replacing ALL of them - go for it while you've got it apart. Old electrolytic capacitors will eventually fail - and new ones will be better than the old ones, even if they are functioning properly.
I'll post pictures of my own project when it's completed.
Take your time, and note well the connection points (photos are helpful, but can also be deceiving - so write it all down too), and it should turn out just fine.