I use boost converters from www.maximic.com . They have some that are pretty small with minimal external parts. (That means less board space.) The one I use is about 87% efficient going from 1.2v to 3v.

When adding batteries, if you combine them in series, you add the voltages. When combining them in parallel, you add the capacity. If you want to add both the voltages and the capacity, then you have to add a set in parallel and a set in series.

You should look at your data sheet for answers to your particular questions. Most batteries are rated at a mimimal discharge current, and increasing the discharge current will decrease the capacity.

Note that if you can figure out a way to run at 3v instead of 5, your batteries will last up to 40% longer--which might allow you to eliminate that second battery. The reason is that your current draw will drop significantly--just look at the PIC data sheet in the Electrical section for current draw at various voltages. When working with small packages, it could be worth the effort. At the worst, you might be able to run the PIC at 3v, and your other peripheral at 5.