It's something of a relic of early-20th-c debates on wiretapping. Some states came to the conclusion that it's "wiretapping" unless both sides of a conversation agree, which has a certain privacy-law type feel to it. In other states, it's only wiretapping if you're doing it unbeknownst to both participants, which is closer to the normal definition of wiretapping, looking more at the "sneaking onto a phone line you don't belong on" aspect rather than privacy concerns.

It can produce some oddities in companies as well. It's now assumed that a corporation can read employees' email, for example, or record their internet or IM traffic. But in a two-party-consent state, it would be illegal for your employer to record telephone calls made from your office phone, unless they get the consent of each person you talk to.