Horse trading is, in the original sense, the buying and selling of horses, also called "Horse Dealing". Due to the great difficulties of evaluating the merits or demerits of a horse offered for sale, the selling of horses offered great opportunities for dishonesty. It was not to be expected that the sellers of horses would fail to capitalize on these opportunities; thus those who dealt in horses have had a reputation for shady business practices.
With the decline in the standards of business ethics in the U.S. in the Gilded Age, however, the activities of horse traders came increasingly to be seen by the business class not as symptoms of the moral depravity of horse traders, but as the natural, and not necessarily wholly undesirable product of a competitive market. Thus, for example, the New York Times in an 1893 editorial criticizing a proposed law to make it illegal for a newspaper to falsely state its circulation figures, declared that "if the lying were stopped by law, the business of horse trading would come to an end, and the country taverns and groceries in the Winter season would be deprived even of the limited eventfulness which they now enjoy."
Such attitudes were reflected in the early 20th century adoption of horse trading as an approbatory term for what others would deem ethically dubious business practices; it is likely the 1898 publication of Edward Noyes Westcott's David Harum -- whose title character saw all business through the lens of horse trading—played a key role in this.
In a further development of meaning, horse trading has come to refer specifically to political vote trading, and this is now the most common sense of the term, largely displacing the older term, logrolling.