As other answerers have said, the idiomatic use of "walk back" describes a backing off or distancing of oneself or one's organization from a statement that one (or it) has made on one's (or its) behalf that has drawn criticism and (often) widespread disapproval. It seems to be especially heavily used in political discussions and arguments.
Merriam-Webster Online doesn't offer a definition for "walk back" in this idiomatic sense, but it does have this entry for the phrase:
walk back intransitive verb : to ease back the fall of a hoisting-tackle while keeping it in hand
It's not impossible that someone familiar with this usage involving the controlled descent of a hoisting tackle might have applied it to a tactical revision of a political position, but most politicians and those who cover them are unlikely to find much resonance in the image of a pulley under hand control. Also, the political sense of "walk back" uses the verb transitively, not intransitively.
Two bits of evidence suggest that the idiomatic usage emerged fairly recently. First, Grant Barrett, The Oxford Dictionary of American Political Slang (2004), which is dedicated to precisely the area of U.S. English where the phrase seems to have arisen, shows no awareness of its existence.
Second, a series of Google Books searches for particular phrases that incorporate "walk back" in the relevant sense go back no farther than 2013. For example, a search for the phrase "walk back his earlier" finds matches for the longer phrases "walk back his earlier thesis" (2013), "walk back his earlier use" (2014), "walk back his earlier statement" (2014) [relevant text not shown in snippet window], and "walk back his earlier assertion" (2015).
The earliest match for "walk back [one's] X" that I found in a series of Google Books searches may not be related to the idiomatic sense that Yoichi Oishi asks about. From Norman Ford, Good Night: The Easy and Natural Way to Sleep the Whole Night Through (1983) [combined snippets]:
You can reschedule your bedtime for any hour you choose. But you should not try to "walk back" your bedtime in increments greater than three hours daily. This usually means you must take seven days off from work to complete the process.
...
If you are able to successfully overcome NS by changing your sleep hours, you might consider experimenting with Technique 7 to "walk back" your body temperature rhythm to a more natural time.
Here "walk back" refers to a systematic, calibrated, interval-based shift over a period of days, figuratively resembling a series of even footsteps that take a person from an undesirable position back to a comfortable and effective one. This has some similarities to the recent political idiom, but it differs in one crucial way: the political "walk back" consistently involves an attempt to recalibrate a message based on unexpected problems with the previous message; thus it is essentially reactionary—a reaction to a reaction. In contrast, Ford's bedtime "walk back" is the product of proactive—not reactive—strategic planning.
The earliest instance of the political idiom that I could find is from Kenneth Timmerman, Shadow Warriors: The Untold Story of Traitors, Saboteurs, and the Party of Surrender (2007):
There was always a dead period between the time you [a reporter] finished a piece and when it came out, and that was when bad things happened. Sources went south. Documents leaked. Government officials panicked and started calling editors, furiously trying to walk back their indiscretions. But when he saw the title to Dana Priest's latest story, “Secret World of U.S. Interrogation,” he feared the worst. He had been scooped.
Other somewhat early instances appear in The Civil Liberties Legacy of Harry S. Truman (2012):
Truman's suggestion to the contrary stuck in the newspapermen's craw and gave ammunition to those who argued he was acting unreasonably. Indeed, Truman's press secretary, Joseph Short, later walked back the president's claim and granted that if the correspondents received news from official channels they could feel safe in running it.And yet the irritation lingered.
and in Carnes Lord, Proconsuls: Delegated Political-Military Leadership from Rome to America Today (2012):
It seems clear that Bremer arrived in Baghdad determined to walk back the administration's established policy concerning an early transition to Iraqi sovereignty. This entailed, however, an American occupation of Iraq lasting — so Bremer seems to have expected — many years, along the lines of the postwar occupations of Germany and Japan.
Conclusions
The image that "walk back" originally intended to invoke is a matter for speculation, but in current usage it refers to something like an orderly tactical withdrawal from a previously stated view, rather than to a headlong retreat amounting to a rout. The phrase does seem to represent a greater distancing than is implied by the idiomatic phrase "step back from."
The earliest Google Books match I could find for "walk back" in its now-common idiomatic sense is in Timmerman's book from 2007—but the expression seems to have penetrated popular culture in the United States only in the past five years.
UPDATE (/18/2016): walking back the cat
Peter M noted in an answer posted on October 20, 2015, that the notion of "walking back" may be tied to an idiom about cats. I have recently found confirmation of that view—and indeed the phrase occurs as "walk back the cat" earlier than the earliest instance I found of "walk back" without a cat. William Safire, Safire's Political Dictionary (2008) has this entry:
walking back the cat In diplomacy, retreating from a negotiating position; in intelligence gathering, examining old analyses in light of new information.
Foreign Service officers use this diplomatic slang, which is similar to the "don off the mountaintop" expression of labor leaders faced with the need to reduce demands. [Cross reference omitted.] When President Carter's chief armaments negotiator, Paul Warnke, was criticized for making an unrevealed concession to the Soviets in strategic arms limitation talks, columnists Rowland Evans and Robert Novak wrote in 1977: "The 600kilometer mystery, therefore, raises suspicions that Paul Warnke will begin 'walking back the cat' on the Carter SALT package, unless checked by the President himself."
A second meaning, in spookspeak, emerged in an 1986 opinion piece in the Chicago Tribune discussing the investigation into the troubling past of Austrian and later U.N. leader Kurt Waldheim: "Intelligence agencies are now 'walking back the cat'—reconstructing events and decisions in light of Waldheim's Nazi past and who might have known and made use of it."
Google Books searches corroborate Safire's comments. For example, from Lawrence Spivak, Meet the Press (1996) [combined snippets]:
And interestingly, in the C.I.A., they talk about walking back the cat, which is taking what we know now and then looking back and seeing how it all happened. Well, to walk back the cat here, [Bob] Dole had said he'd been thinking about this for 45 days. So a month and a half ago, when you were about to ask that question, he was planning this strategy, which essentially is avoid a fight on abortion at the convention, don't rile up the social conservatives on that, but take a position on immigration that was considerably softer than the convention wanted.
And from U.S. Senate Subcommittee on Security and Terrorism of the Committee on the Judiciary and the Subcommittee on Western Hemisphere Affairs of the Foreign Relations Committee, and the Senate Drug Enforcement Caucus, "The Cuban Government's Involvement in Facilitating International Drug Traffic" (April 30, 1983) [combined snippets]:
Mr. LISKER. The cat is out of the bag, so to speak. We are not going to be able to put the cat back in—walk the cat back, as they say. Cuba will not be exonerated from any role in international drug trafficking no matter what information may be developed subsequently.
The instances of "walking the cat back" actually go back to the 1960s. From U.S. Congress, House Committee on Appropriations, "The Budget for 1967: Hearings" (1966) [combined snippets]:
This meant walking the cat back, as it were, on the reductions on automobiles and telephones that became operable on January 1 of this year.
And from U.S. Senate Committee on Appropriations, "Hearings" (1969) [combined snippets]:
Mr. PETTY. In anticipation of the favorable action within the United States, other countries have already commenced, and I guess in the case of 12 countries have concluded, their authorizing appropriating procedures for this replenishment. To get 18 or 19 countries to march down the same road, roughly? in stage is very hard; to contemplate walking the cat back is difficult.
These instances strongly suggest that "walking back" began as the longer idomatic phrase "walking back the cat" or "walking the cat back," and that the idiom originated as U.S. government or military slang. In fact, the earliest match I could find appears in a book by U.S. admiral Walter Ansel, Hitler Confronts England (1960) [combined snippets]:
Political operator Hitler may have reckoned without his host. Once one is committed to an operation of these proportions, holding back is fraught with complications. Walking the cat back can be harder and more harmful than urging her on. The thing gathers its own momentum and rolls of itself. The Fuhrer of the Germans did not know it on 13 July 1940, but on that day, when he coolly sanctioned the Army plan, he surrendered a substantial part of his erstwhile freedom of action.
