In all party consent states, it is illegal to record a private conversation unless everyone who is being recorded is aware and has consented to being recorded. In one party consent states (which are the majority of states), only one person (presumably the person doing the recording) needs to be aware of and consent to the recording.

That difference can obviously make a huge impact on the legal ramifications of recording. For example, during the Monica Lewinsky/Bill Clinton affair, the only person actually indicted for a crime (later dropped) was Linda Tripp, who was brought up on wiretapping charges for surreptitiously recording Lewinsky. This only happened because Maryland is an all party consent state.

This is also why customer service calls start with "This call may be recorded for quality purposes..." - it's to inform you that the call is being recorded if you happen to live in an all party consent state.