Use 60/40 lead-tin solder with a rosin core flux.
I have done it many times and it does work.
First buff the ends of the cell with sand paper, once roughed up the solder will wet better.
The thing with these batteries, (as mentioned above) is they are spot welded.
Soldering them can be tricky, the battery acts as a heatsink and draws the heat from the tip.
Its a ballance of getting the end of the cell hot enough to make the solder wet properly, but not hot enough to damage the venting valves on the cell (keeps the battery from exploding if it gets too hot during charge or discharge cycles) or causing it to rupture. ALWAYS wear safety glasses when working with batteries, especially if you are deliberately applying heat to the cells.
Last pack I made, I merged 2x 3 cell NiMh 1100mAh cordless phone packs to make a 7.2v pack.