A United States presidential election has never ended in a tie in the electoral college. The last time no candidate secured a majority of electors was in 1824, when Andrew Jackson fell some 32 electoral votes short of an outright majority but atop a field of four candidates. The decision was thrown to a contingent election, per the Constitution, as revised by the Twelfth Amendment. Contingent elections are settled in the Congress, with the House voting for president (one state, one vote) and the Senate for vice president (one senator, one vote). John Quincy Adams, the establishment candidate, won on the first ballot in Congress. He was joined though by Jackson's running mate as vice president. When John Calhoun was re-elected vice president in 1828 with Jackson taking the presidency, he joined George Clinton as the only vice president to serve under two presidents. The South Carolina politician had a falling out over nullification with Jackson toward the end of the latter's first term and was dumped from the '32 ticket. The presidential contest has not been decided by contingent election since.
In the last hundred years, only a handful of elections came down close enough in the electoral college that they could've ended up without any candidate winning a majority of electors with a swing of just a few thousand votes; 1960, 1976, and 2000 and 2004. David Leip has "what if" scenarios for those elections at USElectionAtlas.org. For example, 1960 involves about 10,000 votes in Illinois and Missouri swinging from Kennedy to Nixon.
Nate Silver placed the odds of an electoral college tie at .6 percent last month, based on several maps he outlines that are within the realm of possibility and end in a tie. Many rely on Maine's 1st district to go for Romney, giving him an extra electoral vote and unlocking several new configurations of battleground states that would end in a tie. Nevertheless the most likely tie relies on Romney winning neither Maine's 2nd congressional district elector nor New Hampshire. It's not a surprising map at all except for its total:
Such a result would be thrown to Congress, with each state's House delegation being allowed to choose from among the top three vote getters in the electoral college. A third candidate could emerge without winning a state if a "faithless elector" decides to cast their vote for someone other than to whom they were pledged. Not all states have laws against faithless electors, and those laws that do exist remain legally untested. Several states, too, have entered a compact that pledges their electoral votes to the winner of the national popular vote, but that agreement does not go into effect until enough states have signed on to wield a majority (they have 132 electoral votes with 9 states, including California and Illinois, signed on). It's unlikely any state would step in to alter its electoral vote to avoid a tie, as it would require sending electors
to vote for a candidate other than the one that won the vote in that state. Since the GOP takeover the House in 2010, Republicans hold a majority of state delegations in the House of Representatives, meaning a contingent election would likely end up electing Mitt Romney president. The Senate meanwhile, is held by Democrats and would presumably vote for Joe Biden in the case of a tie, making him the third vice president to serve under two presidents and keeping his path to 2016 open.