Campsite visitors. You play games with them and convince them to live there. Then they visit Nook, come back and mention a villager might want to leave. The villager they pick is random. You can keep resetting the game until they choose the one you like, but this could take many attempts and hours of mashing A to skip through the silly games/dialogue.
They spontaneously want to leave. A thought bubble will appear over their head. Talk to them, they will say they're thinking of moving on. Encourage them if you want them gone. This doesn't relate to friendship levels, ignoring them, fencing off their home, pushing, hitting with nets, etc. Again, completely random as far as I know, so you could be waiting forever.
Add a villager with an Amiibo. I don't have any, but supposedly it gives you complete control over who they replace.
Finding a new villager:
The day after an animal leaves, the house will revert to a fenced-off plot of land. At this point you want to visit mystery islands via Nook Miles Tickets. Each visit will spawn a new villager you can ask to stay on your island. The last time I did this I visited twenty islands before I settled for Zucker.
Feel free to correct me if I've got any of this wrong...