Just scuff those spot welded tabs up with some fine sandpaper, and use a 40 to 80 watt soldering iron with a broad tip to tin the tab, as has been mentioned. Raise the tab up on a piece of thin ply wood to help with heat concentration on the tab and not the battery. Then tin the wires, and then make the connection. I sometimes take stripped down Romex solid copper wire and hammer it flat to make a copper bar for connecting batteries. Back in my R/C sailplane and electric days, I made hammer head soldering heads for people's soldering irons and a VEE fixture so you could solder batteries end to end with no connector for powering electric motors. Easy to do, you just need the correct equipment. Those tabs are probably stainless steel, as has already been mentioned, and stainless will require a lot of heat to get to soldering point. Just make sure the solder flows when you do it to avoid a cold solder joint and a point of high resistance. If you go some old cells, practice on those. You need to get it hot FAST so you don't harm the guts of the cell.
Type at you later,
Dan McEntee