You are taking an AC signal from the wall and then as you say, the transformer, recitifier and capacitors are bringing it down to a lower DC voltage. From there, most charging circuits are either linear regulator type chargers or switch mode power supply type regulators (both of those are advanced type links, but just there to see they both exist). They are basically normal DC/DC power converters with some kind of monitoring circuit inside. These two components fulfill the needs you list in number 1 and 2. To learn more about how they work, I'd check out Dave's explanation of linear and switch mode power supplies.
If you're looking to build your own eventually, you'll need to figure out how to do the monitoring with a micro or otherwise and then control some kind of DC/DC power converter. Good luck!
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.
Best Answer
It looks to me as though the op-amp is set up to detect the "delta-peak" condition at the end of the battery's charge curve.
I'd guess that S1 is a momentary push-button type of switch, and it is used to start the charge cycle. When S1 is closed, the op-amp's non-inverting input (+) will be pulled lower than its inverting input (-), forcing the output low. This in turn switches Q1 on, lights D3 & switches Q2 on to charge the battery.
At the end of the charge cycle, when the "delta-peak" condition occurs and the battery voltage starts to reduce slightly (even while charging), the change in voltage will occur quicker at the op-amp's inverting input (-) than at its non-inverting input (+), due to the much smaller value of C4 vs C3. This then has the effect of putting a lower voltage on the op-amp's inverting input (-) than that which is on its non-inverting input (+) which forces the output high - turning Q1, D3 & Q2 off.
R6 & D2 appear to hold the circuit in its off state until S1 is once again closed to start the charge. D6 is placed in parallel with R8 so that C3 initially charges quickly to near the battery voltage when the charge cycle starts, but doesn't allow a quick discharge when the charge is near its end. I agree with Matt B, that R7 & C2 serve as a switch-debounce.