In brief: A battery stores the charge by chemical means, a capacitor by electrostatic means.
In detail: When you charge the battery, a chemical reaction occurs inside it. For example, in a car battery, sulfuric acid and lead turn into lead sulphate when you discharge it, and change back when you recharge it. In a capacitor, when you charge it, you get electrons moving to the surface of the negative plate, and away from the surface of the positive plate. Physically, if you look inside a capacitor, you won't see any phisical changes taking place (in fact you're only shuffling the electrons around), whereas in the battery, you'd be able to see crystals of chemicals forming or dissolving as it is used.
Some capacitors called "electrolytic" capacitors (the ones that look like cans) have an electrolyte inside them just like a battery does, but it's only there to keep the dielectric there, no chemical reactions take place during charging or discharging so it still works like a normal capacitor (but you can't reverse the polarity of the terminals because that would cause it to explode. This is why electrolytic capacitors have a "+" and a "-" terminal, whereas other types of capacitors like polyester capacitors don't mind which terminal is plus and which terminal is minus.").
Now for some differences in their characteristics:
1. The output voltage of a battery remains relatively constant when it's being discharged. For example, if your battery's label says 1.2 volts (as in the case of ordinary Nickel-metal-hydride, i.e. Ni-MH batteries), it gives you 1.4V briefly when fully charged, then quickly falls to 1.2V during discharge, stays at around 1.2V for most of the discharge, and finally starts falling again to about 1V when the battery is empty. Here's a graph showing voltage against time for a battery: http://www.crypto.com/chargers/d401s-3.gif
With a capacitor, the voltage falls continuously during use. You start out with a 12 volt voltage across it, but by the time you've used half the energy in the capacitor, it will already have fallen to one quarter of the voltage i.e. 3 volts. If you want to look at a graph of voltage agains time for a capacitor, here's one: http://www.antonine-education.co.uk/New_items/TRA/images/Sensin1.gif
2. A capacitor can be charged and discharged millions of times with no problem. Batteries only last 500 to 1500 cycles, because all those chemical reactions wear them out!
3. A capacitor can be charged and discharged within a few seconds no matter how large it is, provided you have a powerful enough charger and wires thick enough so that they don't melt. A battery however needs at least 15 minutes (and normally 3 hours) to charge, and there's a limit to how fast you can discharge it too.
but:
4. Batteries store loads and loads of energy. A similarly-sized capacitor can only store a tiny fraction of the energy of a battery. Supercapacitors can store about as much energy as a similarly sized battery, but for some reason supercapacitors aren't very common and I've actually never seen one in action.
You might be thinking that you could use capacitors to power an electric car, but points 1 and 4 above show you that that's impossible because you'd need an incredibly huge capacitor to move your car any significant distance (think a capacitor the size of a 40-foot trailer just to give you the same mileage of a single tank of petrol), and it's also very hard to use because the voltage of the capacitor drops continuously. Basically, if your car uses an electric motor designed for 12V and you charge your capacitor to 12V (since higher voltages will burn out your motor), you'd need a system to boost the voltage that's being fed to the electric motor while the capacitor is being discharged, so that the motor is still getting the 12V it needs even when the capacitor is at only 3V as in the above example.
So capacitors are used basically when you need to store energy for an extremely short time, for example if you want to turn alternating current into direct current you can use a diode (or a rectifier) and then a capacitor to smoothen out the ripple voltage and make it almost constant. Some hybrid cars use capacitors to store the energy they get from regenerative braking. Also some solar powered torches or radios that you crank by hand use a capacitor to store the energy instead of a battery because it's cheaper to use a capacitor (but then the radio only plays for 15 minutes before you have to wind it up again).
Electronics also use capacitors a lot because they can charge them up to a certain voltage and use it as "memory" because the capacitor keeps the same voltage and the device can read the voltage later to remember the information it had stored previously. This is the principle used by your computer's RAM.
And you probably won't understand this, but large factories use capacitors for "power factor correction" since all the electric motors they run are "inductiv