Here's a good video http://www.youtube.com/watch?v=sEXltSby-UU

I see that the contacts are relatively far away from any important electronics, so this should be pretty easy. As everybody has been saying, tin the tip of your soldering iron once it gets hot enough to melt the solder easily. Tinning means that you are coating the tip with molten solder. Now, I would tin the battery leads after tinning the tip. Touch your iron to one side of a lead and touch the solder to the other side, do this till the solder melts and flows over the lead. Remove the iron immediately. Let the leads cool before going any further.
Now, position the battery where you need it, with everything tinned, your solder should flow nicely and prevent a "cold" solder joint. Now that you have the leads through the circuit board, touch the tip of the soldering iron to a lead and the contact on the board simultaneously, touch you solder to the other side of the lead and the contact on the board, do this until the solder melts on both points. Remove the iron immediately. Put the cartrage together and test it out!

Hmmmmm

Looks like I need me some kinda battery clip I guess