Soldering Li-Ion batteries such as 18650 can be dangerous. Overheat can cause the battery to catch fire and explode. If you decide to solder battery, you are doing so at your own risk.
If you are new to soldering, you should check out my beginner tutorial on the subject first.
Use good quality solder with flux core, avoid using additional acid based flux (solder paste) as it will corrode the connection/battery in the long run. See my solder recommendation here.
Discharge Battery First
Before soldering, it’s best to discharge the Li-Ion battery down to 3V. The more energy stored in the battery, the more dangerous when things go wrong. 3V is the minimal safe voltage for 18650 to be discharged to. Even slightly lower voltage is okay but might be bad for the life span of the battery in the long run.
Roughen up Battery Terminals
Before soldering, scratch the top and bottom sides of the cell with sand paper to remove the oxide layer which will help solder to stick to.
Do It Quick
“Tin” both both sides of the batteries with a small amount of solder, let it cool down before soldering the wires to it.
You want to keep the time your soldering iron touching the battery terminals to a minimum (e.g. less than a second). The longer you leave your iron on the battery, the more heat will build up. For this, you want to use a powerful, temperature-controlled soldering iron.
A less powerful iron will not hold the temperature as the heat will simply get sucked out when soldering a big piece of metal. I use the TS100 iron personally, and it works really well.
Finally you want to wrap it with heatshrink, such as this http://bit.ly/2JTOgLy