You'll need a gamebit (I believe it's the 3.8 size for GB and GBC carts, grab the 4.5 one too, they're cheap enough off eBay) a soldering iron, pliers (or something to grab hot metal with) and a replacement battery. I'm not sure what battery a GBC cart uses, when you remove the old one bring it with you to a Radio Shack, the part number should be on it.
The cart should be held together with one security screw. Remove it and it will slide apart. Locate the battery on the cart PCB, heat the solder up with the soldering iron until its molten and use your pliers to remove the battery. Do these steps in reverse to install the new battery.
I've never replaced a GBC battery myself, but I've done plenty of NES ones and I believe the process is quite similar. Someone correct me if I'm wrong. Hope this helps you out.