Legal Stuff

Recording
Federal law allows recording of phone calls and other electronic communications with the consent of at least one party to the call.
A majority of the states and territories have adopted wiretapping statutes based on the federal law, although most also have extended the law to cover in-person conversations. Thirty-eight states and the District of Columbia permit individuals to record conversations to which they are a party without informing the other parties that they are doing so. These laws are referred to as "one-party consent" statutes, and as long as you are a party to the conversation, it is legal for you to record it. (Nevada also has a one-party consent statute, but the state Supreme Court has interpreted it as an all-party rule.)

Twelve states require, under most circumstances, the consent of all parties to a conversation. Those jurisdictions are California, Connecticut, Florida, Illinois, Maryland, Massachusetts, Michigan, Montana, Nevada, New Hampshire, Pennsylvania and Washington. Be aware that you will sometimes hear these referred to inaccurately as "two-party consent" laws. If there are more than two people involved in the conversation, all must consent to the taping.
Regardless of the state, it is almost always illegal to record a conversation to which you are not a party, do not have consent to tape, and could not naturally overhear.
Federal law and most state laws also make it illegal to disclose the contents of an illegally intercepted call or communication.

At least 24 states have laws outlawing certain uses of hidden cameras in private places, although many of the laws are specifically limited to attempts to record nudity. Also, many of the statutes concern unattended hidden cameras, not cameras hidden on a person engaged in a conversation. Journalists should be aware, however, that the audio portion of a videotape will be treated under the regular wiretapping laws in any state. And regardless of whether a state has a criminal law regarding cameras, undercover recording in a private place can prompt civil lawsuits for invasion of privacy.

Identify and date your recordings
If you anticipate the need to provide the recorded message as a proof to a court (get legal advice before hand) you can improve the likelihood for the recording to be accepted as evidence by following those steps:
Dial the first digit of the phone number you are calling, (the phone line is silent - no dial tone) in a loud and steady pace - say your name the date and time.
You can also say the name and phone number of the person you are calling.
Dial the rest of the digits of the phone number.
When the other party of the phone line answers call them by name and mention your name as well ("how are you Mike, Sarah is calling!").

In the event that an incoming call is taking place (somebody called you) do the same. Mention the caller by name and say yours as well.

You can also say the date and time at the end of the call, when the caller hangs up before you do.

The FCC Role
In addition to state and federal laws governing the taping of phone calls, the Federal Communications Commission has its own requirements concerning such taping.
The FCC requires that an individual notify other parties to a call before using a tape recorder in an interstate call. The rule requires that the individual either get consent from all parties before making the call, notify the participants at the beginning of the recording, or use a "beep tone" that is repeated regularly throughout the call.
The FCC rule only applies directly to local telephone companies, but those companies are required to impose similar rules on the public through their customer agreements. The only penalty that can be enforced by the local carrier is revocation of telephone service. (In the Matter of Use of Recording Devices in Connection with Telephone Service)

Broadcasters and the Phone Rule.
Broadcasting a telephone conversation without notifying the other party involved in the conversation is subject to monetary fines or an admonition under an FCC regulation.
The "Phone Rule" states that a person who intends to broadcast a conversation or record a conversation for later broadcast with another party on the telephone must, at the beginning of the telephone call, inform the party that the conversation will be broadcast. No consent from the party is required.
The Phone Rule is enforced primarily against radio "shock jocks," especially those who call people while on the air as part of a practical joke, but the rule has been applied to all kinds of broadcasters, including newsgatherers.
FCC rulings make clear that when a person originates a call to a "call-in" talk show, it is presumed the person knows of the possibility of his or her voice being aired. (In the matter of Entercom New Orleans License, LLC)

Cellular & Cordless Calls
The federal wiretap law was amended in 1986 and 1994 to expand the definition of electronic communications to include cellular and cordless phone conversations. Under the statute, cellular and cordless phone conversations can be recorded with the consent of one party.

The federal law was changed to accommodate the differences between the cordless telephone system and the traditional telephone system, which transmits communications by wire or cable.
In addition to the federal law, the Federal Communications Commission implemented a rule that prohibits eavesdropping on private cordless telephone conversations. The rule states that a person who is not a party to the conversation shall not use a device to overhear or record the private conversations of others unless such use is authorized by all of the parties engaged in the conversation.
Many of the state laws also specifically apply to cellular and cordless calls, and others are broad enough — by covering all "electronic" communications — to cover these methods of communication.