The first, most important step is going to be to get the stranded wire as clean as possible. You won't be able to scrape or scrub it clean - you will need a chemical cleaner. There are several "how-to" pages online like this that describe a simple solution you can make at home. The linked page uses a vinegar-salt solution to act as an acid to clean the wires.
Once the wires are shiny and clean, thread a piece of quality heat shrink onto the cable to protect everything once you're done.
Clamp the wire to the terminal tightly and coat the area to be soldered with flux. Use a torch to heat the wire and the terminal, but focus the heat on the steel strap. Be very careful to not overheat the terminal. They are made from a soft metal with a low melting point, so only apply just enough heat to the wire and terminal to melt and flow the solder.
Also, do this well away from the battery. It would be best to remove the whole cable for safety, but protect any plastic parts and keep heat away from oil and fuel if you can't.
Only use enough solder to fill in the clamped area. Reducing the flexibility of the wire is a concern.
Once everything is cool, slide up the heat shrink and heat it up to tightly seal the end of the wire.
Now, after reading all that, and imagining yourself doing it, consider buying a replacement cable that comes with a pre-attached terminal:
It's going to be cleaner and more durable than what you can do at home, but there is some expense to it (varies from $10 to $90 depending on the car and whether or not its a Volkswagen... Friggin $80 cables....).