Since 1911 the law has required an election not less frequently than every five years. The only exceptions have been during world wars. The coalition government of 2010-15 changed this so that, additionally, an election won't normally occur less than five years after the previous one. The next one is due in 2020.
It is literally true that no PM has been voted out of office by the general public, because we vote for someone to be the MP in our constituency and not for the PM - though we obviously have the likely person very much in mind. But when a PM, e.g. Major, finds that his party no longer has a majority in the House of Commons, he knows he will be unable to continue in office and resigns. The Queen invites the leader of the party with a majority to form a government. In effect the public did vote Major out by taking away the majority that he'd need in order to continue. It was more complicated in 2010 because no party gained an overall majority, and Brown remained in office for a week till it was clear that Cameron could form a government with Lib Dem support, when the Queen asked him to form it and Brown resigned. Ex-PMs can if they wish remain in Parliament as back-benchers (if they've retained their seat), as Heath and many others did in the past, but these days they mostly decide to move on to something else.