As it turns out, the State Department has a web page dedicated to answering this very question. Here's what it says:
As explained in greater detail in 11 FAM 721.2, there are two procedures under domestic law through which the United States becomes a party to an international agreement. First, international agreements (regardless of their title, designation, or form) whose entry into force with respect to the United States takes place only after two thirds of the U.S. Senate has given its advice and consent under Article II, section 2, Clause 2 of the Constitution are "treaties." Second, international agreements brought into force with respect to the United States on a constitutional basis other than with the advice and consent of the Senate are "international agreements other than treaties" and are often referred to as "executive agreements." There are different types of executive agreements.
So, a treaty is a kind of executive agreement, one in which two thirds of the senate has provided "advice and consent." That language comes from Article II, Section 2, Clause 2 of the Constitution. This clause defines the procedure and authority for creating treaties. Its text:
He shall have Power, by and with the Advice and Consent of the Senate, to make Treaties, provided two thirds of the Senators present concur...
This clause defines the procedure and authority for treaties, but not so for other executive agreements. However, the State Department web page did mention something called "11 FAM 721.2". I Googled that and found this page, and as it turns out, section 721.2 goes into more detail about the difference between treaties and executive agreements.
This page outlines three kinds of executive agreements that are not treaties:
(1) Agreements Pursuant to Treaty
The President may conclude an international agreement pursuant to a treaty brought into force with the advice and consent of the Senate, the provisions of which constitute authorization for the agreement by the Executive without subsequent action by the Congress;
(2) Agreements Pursuant to Legislation
The President may conclude an international agreement on the basis of existing legislation or subject to legislation to be enacted by the Congress; and
(3) Agreements Pursuant to the Constitutional Authority of the President
The President may conclude an international agreement on any subject within his constitutional authority so long as the agreement is not inconsistent with legislation enacted by the Congress in the exercise of its constitutional authority. The constitutional sources of authority for the President to conclude international agreements include:
(a) The President's authority as Chief Executive to represent the nation in foreign affairs;
(b) The President's authority to receive ambassadors and other public ministers;
(c) The President's authority as "Commander-in-Chief"; and
(d) The President's authority to "take care that the laws be faithfully executed."
Essentially, the President can enter an executive agreement without the "consent and advice" of two thirds of the senate if a previous treaty or legislation gives him the power to do so, or if he is doing so according to another constitutional duty.