It randomly happens. It ends up in the water, and you must fish it out. If you do not find it in time, the villager just finds it on their on, and their friendship with you does not decrease. Not sure if it increases if you find it, most likely does, and I think they give you a gift to thank you as well. Hope this helps.
Well, besides finding the key, the villager will reward you as well. Sometimes an item, and sometimes with bells. I got 650 bells for rescuing Gala's key last time. Also, I've found that some villagers are more prone to lose their keys than others. As long as you get it the same day they lose the key, you'll get a reward and I think it also raises your friendship level with that villager. If you can't find it, and it's pretty easy, just look for the smaller fish, not the tiny one though. You'll probably get a few fish first. If they live in the lower part of town, their key usually can be found in the lower river, and if they live above, the upper river is a good bet for them.
Once in a great while I'll have to try the opposite, but usually this holds true. Sometimes I find it right away, and sometimes I have to catch a few fish before it shows up.
If you've just started your game or town, I personally think it's a good opportunity to work on your fish encyclopedia, (especially when it happens in the summer). The first time it happened in my town, it took me about 30 minutes to find the key - I didn't know which size to look for so I just caught any fish I could in the river - and I must've added 10 fish to my encyclopedia after that.
Town 1: Nocturne/ Town 2: Zephyr
See profile for games I Wifi In :)