I've only tussled with the legendary beaver a few times (they seem ridiculously rare), but I tried one strategy and it worked each time.
When I noticed them, I saw where they liked to go to land. I backed off a bit (just outside of being able to see them, when I've zoomed out the map), started sneaking, hid behind a tree and let an hour or so go by.
When I burst back into that area I always found them quite far inland (about the centre of the tile area), then instead of going towards them, I moved to between them and the water. Every time for me, they panicked and tried to run past me. I found them slow and was able to club them fairly easily. One time, one of the beavers made it past (I got distracted watching their movement), but the next day it was back to the same area and was an easy kill.
It's possible I've been lucky... but I suspect that, similar to seals, they have a favourite shore they like to use.
Edit: Regarding tracking. One of my characters was good enough to see the tracks and that was easy. Other times, I used my seal strategy, which is to spot them on the water (on raft or punt), back off, let them move around, back off if they get close again, repeat. You might have to zoom out and come back again in an hour, but usually you get a sense of where they like to go.