The alternative vote seems like an excellent replacement for the first-past the post voting system. Per the answers on this question, I understand some of the reasons of why it hasn't been implemented in the USA but my question is, if the American people rally and really want to replace "first past" with "Alternative vote", what needs to happen?
Each state can decide individually how they elect their federal representatives (house of representatives, senators and electoral college members which vote the president) and how to elect their own legislature. Those election systems are described in the respective state constitutions which have their individual change processes.
So when you want your state to adopt a different voting system, you would have to look up how constitutional changes work in your state.
Elections on county and city level are often also governed by their respective constitutions.
Some lower levels do experiment with alternative voting systems like proportional-representation or instant-runoff (which goes further than alternative vote by allowing voters to rank all available candidates in order of preference). So when you want to lobby for experiments with new voting systems, you have a better chance of success when you start on the local level.
Keep in mind that in most states/cities/counties, the people who need to approve of constitutional changes are the same people who got into the positions where they currently are through the current system, and by agreeing to this change they reduce their own chance of getting re-elected and that of their peers. So when you assume that politicians are perfectly rational beings (cough), the only way to make them agree to a legislation which weakens their chance of re-election would be when public support for it would be so overwhelming in quantity and quality that not supporting it would weaken their re-election chance even more.
To answer the specific question - on a national level, this would require a constitutional amendment, as the US constitution spells out the mechanism of elections.
Same goes for state level elections - would require a state constitutional amendment.
Both are fairly involved processes, requiring a lot of yes votes from a lot of voters.
And now, for practical reality:
In the US, the current political layout of two dominant parties would tend to make a runoff style election almost meaningless. The two current parties represent very different political outlooks, and any other parties draw almost no votes. So a runoff between the two would produce about the same results as the initial election. Do you see a voter switching from repub to dem or vice versa, just because the vote was close? Probably not. And the small third parties: libertarian, green, etc... don't draw enough votes to tip an election in anything but an extremely close margin.
In other democracies, such as the UK or Germany, two parties don't dominate. It is quite possible that during a runoff, a Green party supporter might swing to a Liberal Democrat, as they are similar in philosophy, especially if the Liberal Democrat made some commitments to the Green platform to draw their support.
Looking back at the 2016 US election with two very odious choices, a third candidate might have actually made some headway. Sadly, the only third party that had any traction at all, the Libertarian party, fielded a complete moron. (what is Aleppo?) Oops.
So, to answer the question in a more pragmatic manner: to get a runoff style election in the US that actually has meaning, the electorate would have to break the two party mindset. Enough voters would have to be willing to support other parties in sufficient numbers to add meaning to a runoff election. Given the two primary choices in the 2016 election, that's no longer a far fetched scenario.