Interestingly, I'm working a similar problem right now and am considering starting my own thread...

Unless you are committed to using a PIC, take a look at the MAX 712/713. It works well enough but I think you might need a higher-voltage power supply, regardless of what you use to charge it. Several years ago (many years ago?) Melanie discouraged creating a PIC-based solution when chips such as the MAX 712 were available.

On the other hand, there is something to "rolling your own"...

If you are committed to using a PIC and want to keep it really simple, consider the humble LM317. NiCads are fairly forgiving in their charging (although mostly I use NiMH so that's really the impression I've gotten rather than experience), and you just need to pump them with a constant current until the voltage plateaus (i.e., stops increasing). The datasheet for the LM317, on page 18, shows an example 1A constant current source. Substitute your battery for the load, add another little regulator for the PIC, put an ADC on the top of the battery (through a voltage divider) and the rest is just programming... Read the MAX712 datasheet as an instruction for how it should operate.

The problem I'm having is that the LM317 is throwing more heat than I am comfortable with sealed in an aluminum box. Not horrible for a lot of situations, but more than I really want to keep in my particular application.

Hope this helps...

Best Regards,
Paul