Last time i was encountering some spiders, and they inflict my heroes
with strength damage. When i move the cursor over it, it says permanent
STR damage. So how can i cure such debuffs?

Camping removes it.

Edit: You must ensure that "Remove negative effects on rest" is enabled in options.

You can remove it also with the "Treat Ailment" skill of some characters, but also only after resting. Also the Ability damage will wear off after multiple days of resting if you have not the option on, that Hickory mentioned. There are also cleric spells for that, but i think they beginn at spell level 3.

Lesser and greater restoration also work. Lesser restoration becomes available very early if you have a cleric in your party.

Restoration spells from npc or pc clerics

And you must differenciate between the different "permanent" damages. Some are curses, some are whatever. Yours you will lose over time, especially, when you sleep in the outpost.
I, for example, battled some witch tree. After the fight i had gained the "permanent level drain". I had a hard time, until i learned, that this thing was only removeable with some special level 4 spell...