In terms of optimizing battery life, it's obvious you want to keep the average current drain as low as possible, even though there may be significant peaks. For example, lets say you have a wireless device that is supposed to report back periodically via Bluetooth. To do that, the microcontroller and Bluetooth transceiver may have to be on for 100 ms and use 50 mA of current. For now, assume the current drain at other times to be 50 µA (which we'll ignore for now).
If this occurs ever second, then your average current drain is approximately 50 * 100 / 1000 = 5 mA. But if you report back every minute, it is approximately 50 * 100 / 60000 = 83 µA. And if every hour, only 1/60 of that (1 µA). Now that 50 µA sleep current becomes very significant and must be factored in.
If you have a battery with a 600 mAh capacity, then in the second case, your battery would last approximately 600 / (0.083 + 0.50) = 4511 hours or about half a year. Actually it won't be that long, but you can probably count on at least four months.
So the current drain when the unit is sleeping is very important. You want to shut down all your peripherals, and put the microcontroller to sleep. Many microcontrollers have a sleep mode where they can still have a clock running and use only a couple of microamperes. In your circuit design, make sure there are no pull-up resistors for example that are draining current continuously when the device is supposed to be sleeping.
If you device has a display, and it has a backlight, the latter will probably be the biggest power hog in the system. So use a timer and keep the backlight off as much as possible.
A Li-Poly battery, like the ones used in a cell phone, is usually a good choice. Get as big a battery as your budget and physical constraints can afford. Most cell phones have batteries between 1500 mAh and 3000 mAh. (The iPad, on the other hand, is essentially a battery with a display on top, and has a capacity of 11.5 Ah or 11560 mAh.)
It is crtically important that you use a charger management chip that is designed to work with Li-Ion or Li-Poly batteries. I have had good success with the bq24014, and have several products out in the field using it. The bq24230, a newer chip mentioned in a comment by @mkeith, also looks like a good choice.
When using either of these, you want to get a battery with three terminals, where the middle terminal is connected to a thermistor. This will allow the charger chip to monitor the temperature inside the battery. Also, when doing case design, don't squash everything together so there is no room left above or below the battery. Some Li-Poly batteries have a tendency to balloon out a bit after a while, and if there is no expansion room to allow for this, you case could crack.
The charger chip will contain all of the protection circuitry you need. The battery is charged in three phases: conditioning, constant current, and constant voltage.