moving the plates farther apart or making them larger
That will change the capacitance, not neccessarily make them hold the charge for a longer period of time. The other stuff you said was for the most part true.
On another note, capacitors can actually gain charge over time by picking up free electrons from the air. Even if a capacitor has been sitting on a shelf for a long period of time, it is always a good idea to discharge the capacitor by shorting it.
And no, a 9V battery wont make it hold 9V worth of "energy". The amount of energy it stores is dependent on its capacitance as well as the voltage (u=1/2cv^2) . You can have plates 3 miles apart with a 9V potential difference and have it store more energy than having the plates 2 millimeters apart (granted the plates would have to be pretty damn big). That said, don't base the energy contained in a capacitor on the voltage alone.
A capacitor on a power supply is usually packed with a paper insulator betweent he plates
Ehhh, its more of a grease kind of crap. Open up a capacitor one day, it's pretty cool