I was thinking of having my guitar (with a maple fretboard) refretted, but I've been looking at images of different fret wire online, and I noticed that they have some sort of teeth to keep them in place. Does that mean that the fretboard can be damaged when the old frets are removed? It's not an expensive guitar, but it's out of production, so I wouldn't be able to easily replace it if things go wrong.
When removing frets damage to the fretboard is always a consideration, some kind of chipping as the old frets come out is something to be anticipated, rather than disregarded. There are various ways to repair fretboard damage that happens in the process of a re-fret, and a good luthier will have plenty of tips and tricks to both minimise damage and repair damage when it happens.
In reality, it's not generally too bad, with damage mostly restricted to less than the new frets width, ie. not visible and not anything that would affect a guitar in terms of playability. The occasional larger chip can be filled, that's easy to make invisible on a rosewood, on a maple you may see the filler in the odd spot but it shouldn't be too much of a worry if you use a good luthier. I'm talking a mm squared or so at worst, if the luthier is careful.
So generally, yes taking out old frets can cause damage, skill can reduce this but not eliminate it but repairing little chips is easy enough and part and parcel of a refret for someone that knows what they are doing, and won't affect the guitar playability. Certain guitars have frets that were inserted sideways and knowing that a luthier can anticipate what to expect in terms of chipping. Most guitars have frets that come in from the top. A good luthier will know what they are doing, and know how to tidy up after fret removal, so don't worry too much on anything but a super expensive vintage instrument.
Note: in terms of choosing frets, the fret tang width is a consideration, and best left to a luthier, though on a guitar with a truss rod much less of a big deal than eg. a nylon acoustic.