So how should I go about cleaning a soldering tip sponge?
I usually just shake out the bits of solder, and toss it when it gets too worn out. Considering that you can get suitable soldering sponges in 6-packs at the dollar store (and can cut them into quarters if you want a pack to last longer), this is not usually a huge deal.
I use brass wool like this: http://www.gotopac.com/599B_02_Tip_Cleaner_p/599b-02-hak.htm. Though you can just use the wool alone, you don't necessarily need the holder for it. It's a bit more expensive and replacement wool is under $5 and it tends to last longer than a sponge.