The key here is ordering the battery. We found ours at the NICD Lady, a Sanyo KR-600AE with solder tabs. As of 7-29-2009, you could find it on this page: http://www.nicdladyonline.com/shop/?shop=1&cat=13
As far as I can tell, all NiCD cells are 1.2 volts, and this one appeared to be almost exactly the right size. Since the toothbrush can hold enough charge when new to go for a week without recharging, we figured that even if these didn't exactly match the capacity of the original NICD cells, they ought to work.
Because the device was designed for NICDs, you ought to replace the battery with a NICD.
Beyond that, you need a soldering iron, solder, maybe an X-acto knife, some long-nosed pliers, a hemostat (we used a paperclip instead), and some electricians' stable.