To measure the capacity of a battery it takes to discharge the battery using a resistor or any other load until the voltage drops to the minimum value, and record the current and voltage across the load during the discharge process. Then build a graph using collected data, and the capacity of a battery can be calculated from this data. But here is a problem  during discharging process the current across the load resistor dropping down, therefore we will need to integrate the data over time, so this method is not accurate.
But if we will discharge the battery through a current source, then we can find out the capacity of battery much easily and more accurately. But here is the other problem: the voltage across a battery (1.2...3.7 V) is not enough to power the current source. This problem can be solved by using an additional voltage source.
Fig. 1. Circuit diagram used to measure the capacity of battery
V1  a cell or battery to be tested;
V2  secondary voltage source (e.g. a power supply source based on IC 7809 or similar), it must provide current higher than discharge current ;
PV1  voltmeter;
LM7805 and R1  current source;
VD1  protection diode 1N4004 (for currents less than 1 A).
The circuit diagram used for battery capacity measurement is shown in fig. 1. Here we can see the battery to be tested V1 is connected in series with the current source (the current source is based on the voltage regulator LM7805 and resistor R1) and with the other voltage source V2. Note the polarity of V1 and V2: because they are connected in series, therefore their summary voltage is enough to power the current source. The minimum operating voltage of the current source is 7 Volts (5 V is the voltage at the output of the LM7805, across the resistor R1, and 2 V is the minimum operating voltage between input and output of LM7805). The summary voltage of V1 and V2 is not less than 9 V, it is more than operating voltage of the current source.
Instead of LM7805 you can use any other voltage regulator, for example, LM317 (its output voltage is 1.25 V and minimum dropout voltage is 3 V). In this case the operating voltage of the current source is 4.25 V, so we can use the power source V2 with voltage of 5 V. With LM317 the current can be calculated with this formula: I = 1,25/R1.
Then, for example, for the discharge current of 100 mA the value of R1 is around 12.5 Ω.
In the beginning, match the value of resistor R1 to set desirable discharge current. In most cases the discharge current is equal to the battery operation current. Note that some voltage regulators LM7805 and other may consume additional current of 2...8 mA, so it's better to check the current using an ammeter. After that, connect fully charged battery to the circuit board, turn on the switch SA1 and note the time. Watch the voltmeter (PV1) reading. When the battery voltage gets a minimum value, turn the switch SA1 off and note the time again. Remember that deep discharge may shorten the battery life or damage it!
By multiplying the discharge current (in Amperes) by discharge time (in hours) we can calculate the capacity of the battery (in Amperes per hour):
C = I * t
The minimum battery voltage is different for different types of battery. For example, for Nickelcadmium battery (NiCd) a minimum voltage is 1.0 V, for Nickelmetal hydride battery (NiMH)  1.1 V, for Lithiumion battery Liion)  2.5...3.0 V. For every specific model of battery this parameter may vary, so check the documentation of a battery.
Let's consider a practical example how to measure the capacity of battery.
The battery NB11L (see fig. 2.) was purchased from DealeXtreme for 3.7 dollars (SKU: 169532). The brand is unknown. It's marked capacity is 750 mAh. But the item description on the site shows only 650 mAh. What's the real capacity of this battery?
Fig. 2. Liion battery NB11L of unknown brand with marked capacity of 750 mA*h
Fits CAN.NB11L 

We need two contacts to connect wires to the battery. Let's make them out of paper clips. Bend paper clips as shown in fig. 3 and connect to "+" and "" battery terminals (see Fig. 4.). You got to be very careful to avoid short circuit, because it can damage the battery. It is better to isolate clips, and left only tips exposed.
Fig. 3. DIY contacts used to connect 
Fig. 4. DIY contacts 
For the capacity measurement of the battery NB11L, the discharge current was set at 100 mA. It means that value of R1 is just a little bit above of 50 Ohms. The power dissipation across the resistor R1 can be calculated with this formula: P = V^{2}/R1, where V is the voltage across R1. In our case P=5^{2}/50=0.5 W. Voltage regulator LM7805 must be used with a heat sink. If there is no any suitable heat sink around, a glass of cold water can be used as a heat sink  just dip the LM7805 in the water, but keep pins above the water level (in case of TO220 package).
After fully charged battery NB11L was installed into the test circuit board and the switch SA1 was closed, the voltage across the battery were recorded every 30 minutes using the voltmeter PV1. After that, the discharge graph was drawn (see Fig. 5).
Fig. 5. Voltage across the battery NB11L in the discharge process by the current of 100 mA.
From the graph shown in Fig. 5. we can see that it took almost 5 hours (at the current of 0.1 A) for the voltage across the battery to drop to 3 Volts. At the end the discharge voltage declines faster. Now we can calculate the battery capacity:
C = I * t = 0.1 * 5 = 0.5 A = 500 mA*h.
So the real capacity of the battery NB11L of unknown brand is 1.5 times less than it is marked capacity.