It depends. On what? On how a judge feels on a given day.
That is to say, we are not sure.
Conventional wisdom says that we should be cautious and assume that the law of the stricter state will apply. But some commentators argue that the law of the state where the recording device is located should apply.
I found this discussion to be the most complete one-stop place for a nice summary. http://www.rcfp.org/reporters-recording-guide/interstate-phone-calls. I'm going to paste it here because I can and because SE likes that.
Interstate phone calls Date: August 1, 2012 In light of the
differing state laws governing electronic recording of conversations
between private parties, journalists are advised to err on the side of
caution when recording or disclosing an interstate telephone call. The
safest strategy is to assume that the stricter state law will apply.
For example, a reporter located in the District of Columbia who
records a telephone conversation without the consent of a party
located in Maryland would not violate District of Columbia law, but
could be liable under Maryland law. A court located in the District of
Columbia may apply Maryland law, depending on its “conflict of laws”
rules. Therefore, an aggrieved party may choose to file suit in either
jurisdiction, depending on which law is more favorable to the party’s
claim. In one case, a New York trial court was asked to apply the
Pennsylvania wiretap law — which requires consent of all parties — to
a call placed by a prostitute in Pennsylvania to a man in New York.
Unlike the Pennsylvania wiretap statute, the New York and federal
statutes require the consent of only one party. The call was recorded
with the woman’s consent by reporters for The Globe, a national
tabloid newspaper. The court ruled that the law of the state where the
injury occurred, New York, should apply. (Krauss v. Globe
International) The Supreme Court of California in Kearney v. Salomon
Smith Barney applied California wiretap law to a company located in
Georgia that routinely recorded business phone calls with its clients
in California. California law requires all party consent to record any
telephone calls, while Georgia law requires only one party consent.
The state’s high court, applying choice of law principles, reasoned
that the failure to apply California law would “impair California’s
interest in protecting the degree of privacy afforded to California
residents by California law more severely than the application of
California law would impair any interests of the State of Georgia.”
In another case involving Pennsylvania law, four employees of The
Times Leader, a newspaper in Wilkes-Barre, were arrested after they
printed a transcript of a telephone conversation between a columnist
in Pennsylvania and a murder suspect living in Virginia that was
recorded without the suspect’s permission. The Virginia and federal
statutes allow one party to record a conversation, while Pennsylvania,
as discussed above, requires the consent of all parties. The man asked
prosecutors to charge the journalists under the Pennsylvania law. The
court eventually dismissed the charges against the newspaper staff —
but on the unrelated ground that the suspect had no expectation of
privacy during his telephone interview with the columnist.
(Pennsylvania v. Duncan) Federal law may apply when the conversation
is between parties who are in different states, although it is
unsettled whether a court will hold in a given case that federal law
“pre-empts” state law. In Duncan, the newspaper argued that the
federal law should pre-empt the state statutes, because the telephone
call crossed state lines, placing it under federal jurisdiction.
However, in that case, the court did not address the pre-emption
issue. Moreover, as noted above, either state may choose to enforce
its own laws.