This question, which appears simple and direct, is actually filled with subtlety and complication. First, the definition of a battery must be established. There are a variety of chemical and mechanical devices that are called batteries, although they operate on different physical principles. A battery for the purposes of this explanation will be a device that can store energy in a chemical form and convert that stored chemical energy into electrical energy when needed. These are the most common batteries, the ones with the familiar cylindrical shape. There are no batteries that actually store electrical energy; all batteries store energy in some other form. Even within this restrictive definition, there are many possible chemical combinations that can store electrical energy--a list too long to go into in this short explanation.
There are two fundamental types of chemical storage batteries: the rechargeable, or secondary cell, and the non-rechargeable, or primary cell. In terms of storing energy or discharging electricity, they are similar, it is simply a question of whether or not the chemical processes involved permit multiple charging and discharging.
Before answering this question it is also necessary to distinguish between a galvanic cell and a battery, as I have defined it. The former is the fundamental unit of electrochemical storage and discharge. A battery is comprised of at least one but possibly many such cells appropriately connected. Because the cell is where the actual action of storage and discharge takes place, this answer will concentrate on what happens at that level.
All electrochemical cells consist of two electrodes separated by some distance. The space between the electrodes is filled with an electrolyte--an ionic liquid that conducts electricity. One electrode--the anode--permits electrons to flow out of it. The other--the cathode--receives them. The energy is stored in the particular compounds that make up the anode, cathode and the electrolyte--for example, zinc, copper, and SO4, respectively.
Assuming the battery has acquired its charged condition either by recharging or manufacturing, the aggregate effect of the chemical reactions taking place between the anode and the cathode discharges electricity. The anode undergoes what is known as an oxidation reaction: during discharge two or more ions from the electrolyte combine with the anode to form a compound and release one or more electrons. Simultaneously, the cathode undergoes a reduction reaction wherein the material the cathode is made of, ions, and free electrons combine to form compounds.
Simply put, the chemical reaction at the anode releases electrons and the reaction at the cathode absorbs them. When the electrical path provided by the electrolyte and an external electrical circuit connects the anode and cathode, the two simultaneous reactions proceed and the electrons freed at the anode travel through the external electrical connection and react chemically at the cathode to make the cell function. The cell can continue to discharge until either or both of the electrodes run out of reagents for their respective reactions. In a primary cell this means the end of its useful life, but in a secondary cell it just means it is time for a recharge. For secondary cells the recharge process is the reverse of the discharge process. An external source of direct electrical current supplies electrons to the anode and removes them from the cathode, forcing the chemical reactions into reverse until the cell is recharged.
The above constitutes a simplified explanation of how the electrochemical energy stored in a cell is removed as electrical energy in the process of discharging and restored in the process of recharging a secondary cell. There are many more electrochemical and thermal processes taking place at the same time and for most practical cell combinations packaged in the form of batteries it is not possible to completely characterize all of the processes. Therefore, this approximation of the primary reactions is only a brief explanation of what actually happens although it should serve to illustrate the fundamental principles at work.