In my PIP-Watch project I will use a Li-On battery to provide power. Li-On batteries are easy to use in hobby projects: they are light, small, with high capacity, and they come in variety of sizes. Most (not all) Li-On batteries have nominal voltage 3.7V, hence you can directly power your standard 3.3V digital logic directly, using only a simple low-drop linear regulator (e.g. LD59015).
For my first experiments I chose Nokia BL-4C Li-On battery. It’s nominal voltage is 3.7V, charging (maximal) voltage is 4.2V, the capacity is 860mAh.