Не только в русском языке, но и во многих других слово «правый» используется как для обозначения стороны, так и в значении «правильный, имеющий право, достойный уважения», а «левый» - это неправильный, странный, зловещий, неуклюжий. Например, на латыни (и в других языках, сохранивших латинские корни) sinister - это левый и зловещий, на французском gauche - левый и неуклюжий, по-русски левый - это находящийся слева, а также неофициальный (левый заработок), посторонний, не относящийся к делу (левый трёп, левые отмазки, левый чувак), неправильный (встать с левой ноги) и т.д.
Некоторые ученые утверждают, что НЕТ НИ ОДНОГО языка в мире, где слово «левый» имело бы положительные ассоциации. Вероятно, это связано с тем, что многие языки произошли от одного и того же древнего пра-языка. В частности, лингвисты смогли достаточно полно восстановить прото-индо-европейский язык, на котором говорили в Евразии примерно за 3000 лет до н.э. и от которого произошло более половины современных языков. Удивительным образом в этом языке было слово «правый», но не было слова «левый». Это кажется невероятным, ведь если было само различение «правого» и «левого», то почему же для левого не было отдельного обозначения? Предполагают, что «левое» ассоциировалось с чем-то запретным, о чем даже нельзя говорить. Возможно, именно поэтому позже во многих языках возникало по несколько различных слов для обозначения левого (например, на латыни есть слово sinister и более древнее – laevus, оба они значат «левый»).
Моя версия, конечно, не является основной, но полезно вспомнить еще, что согласно поверьям, с правой стороны человека сопровождает ангел-хранитель, а с левой находится бес-искуситель. Следовательно, изменяя, человек соблазняется бесом. Слово "левый" также часто используется, как антоним правому, правильному, обозначая нечто некачественное, сомнительное, неправильное.
Следует также добавить, что, согласно этикету, место справа и по сей день считается более почетным. Поэтому дама должна идти справа, даже если у кавалера и нет шпаги.
Насколько можно судить, эта идиома не интернациональна. В английском, к примеру, самый близкий аналог - "two-timing" (не знаю, как лучше перевести), а немцы те и вовсе совершают прыжок в сторону.
Есть еще интересная легенда из города Эфеса, Турция.
На главной улице города, по обе ее стороны, стояли библиотека и бордель. Библиотека справа, бордель, соответсвенно, слева. Мужчины говорили женам, что сегодня проведут время в библиотеке, а сами благополучно топали налево — в бордель. Еще строения якобы были связаны подземным тоннелем:)
Отсюда и выражение.
Кавалер-офицер вел свою даму под руку, находясь слева от неё, в связи с тем, что на его левой стороне висела шпага. Следовательно правая сторона кавалера - занята его дамой, а левая свободна, куда он от своей дамой и уходил.