A laptop battery is liable to be a good choice if the Li-ion characteristics suit you. These may have 2 or 3 or 4 cells in series. Some provide access to all cell connection points, some don't. Those that don't may have an internal controller to maintain cell balance.

If this is a one off or low volume application you may want to look at using whatever the related laptop uses. If this is for large volume use then Digikey and others sell a range of suitable ICs. An alternative is to use fewer cells and a boost converter. There are many LiPo single cell batteries available for tablets/phones/pdas/ ... . There are numerous 2 cell batteries available for cameras. These are usually dearer per capacity unless you buy aftermarket batteries. An advantage of a camera battery is that there are usually low cost aftermarket chargers available which target a particular camera battery type and which do a good enough [tm] job of battery charging. The price of such chargers is often low enough that building in a commercial charger into a product may be $ attractive.

If you want 12V minimum then you will need 4 Li-ion cells - about 12V minimum (you choose) and just under 17V fully charged.

A possible alternative are sealed lead acid cells. Cheaper per capacity but lower mass and volume energy densities and lower cycle life in deep discharge use.

LiFePO4 (Lithium Ferro phosphate) has lower voltage per cell than LiIon and lower energy density but potentially much greater cycle life. Long term LiFePO4 offers best cost pe cycle but initial price is high.

NiMH - not recommended.

Added:

Florin commented:

Since at this stage I don't need a lot of energy stored in the battery, the single Lithium cell + booster circuit idea sounds really appealing, especially since I can easily find a housekeeping module that does the charging while also feeding DC to my device. Of course, now I have to find a suitable booster; ideally something based on an IC with few components around it. Amperage requirements are pretty meager. I need to build two, one for 5V and another for 12V.

This IC will provide up to 80 mA AT 18V (100 mA+ AT 12v) or 280 mA at 5V out from a single LiIon or LiFePO4 cell. In stock at Digikey for ~ $2/1.

TI / NatSemi LM4510 Synchronous Step-Up DC/DC Converter with True Shutdown Isolation

Efficiency is "OK" across a reasonable load range.

And circuit offers a bearable level of complexity.

An evaluationkit is available - whose PCB gives good pointers to proper layout:

A single Li-ion or LiFePO4 cell will power this well. The latter has lower energy density but has the advantage of longer cycle and better table manners generally. A Li-ion 18650 cell (as used in most laptop battery packs) will give about 7 - 9 Wh when new or say 6 Wh after boost conversion. A LiFePO4 18650 cell will give about 50% of the energy content of a std Li-ion cell. Say 3.5 to 4 Watt hours.

90.5% @0–100% SoC

for electrolyte type A

89.1% @0–100% SoC

for electrolyte type B

I read reverse calculated this from graphs in a non-public measurement report where 2 different types of battery electrolyte (solid/gel) technologies were compared for a 0 to 100% SoC (state-of-charge).

Battery measurements were taken by a technical university, at 21ºC room temperature during 1 month, the year 2013, comparing the results from 150-180 discharge/charge cycles. Batteries under test were all in the range between 5 and 10Ah.

• charging curve: CC-CV
• charge to discharge point: V = 14.375V and I < 0.30A
• discharge to charge point: 0% SoC
• resting period: not specified
• 0% SoC was defined as discharge voltage reached 10.8V (1.8V per cell)
• 100 SoC was defined as charge voltage reached 14.375V (2.396V per cell)
• charge was done at a rate of 0.3C (+/- 0.05C)
• discharge was done at a rate of approximately 0.1C (fixed resistor was used)

The result between charging and discharge power was (remarkably) about 1.6Wh for both battery types, where one battery had a remaining capacity of approximately 40Wh and the other 20Wh.

Some data read back from the graph (resulting in lower accuracy) for electrolyte technology A:

Cycle   Charge [Wh]   Discharge [Wh]
1       100           91
2       100           88
3       100           86
4        97           81
5        92           76
6        86           73
7        81           69
8        78           67
9        74           64
10       73           63
11       70           61
12       69           59
13       65           56
14       63           55
15       61           52

136      44           40
137      44           40
138      44           40
139      45           40
140      45           40
141      43           40
142      44           40
143      45           40
144      44           40
145      44           40

According to my opinion the last measurements are more significant than the first measurements due to the initial formation process. Average last 10 cycles power charged into the battery is 44.2Wh. Average last 10 cycles power discharged from the battery is 40.0Wh.

Some data read back from the graph (human graph point via line to value translation) for electrolyte technology B:

Cycle   Charge [Wh]   Discharge [Wh]
1        85           75
2        83           72
3        80           70
4        78           69
5        76           67
6        76           67
7        75           67
8        75           67
9        74           66
10       74           66
11       73           65
12       73           66
13       72           66
14       72           65
15       73           64

136      25           22
137      25           22
138      25           22
139      24           22
140      25           22
141      24           22
142      25           22
143      25           22
144      25           22
145      24           22

Average power charged into the battery during last 10 cycles is 24.7Wh. Average power discharged from the battery is 22.0Wh.