The Naomi DIMM has a 3 wire battery pack consisting of small PCB and 2 x Panasonic CGR18650H cells. The H is probably some rating, I used CGR18650CF's which have a bit better capacity. Search for CGR18650, or just 18650 and you should be able to source some locally.
The pack is connected like this:

Open the DIMM and disconnect the battery pack:

Strip off the outer plastic, and you should end up with this:

Desolder the PCB, be careful not to short the battery:

Assemble the new cells with the cell spacer and some electricians tape. Solder the metal part from the old battery pack to the new cells.

Add some more tape:


Solder jumper wires to B-, B+, and BC.

Tape it up, and you're done:

Thanks to InvZim of KC for this :smt007