The phrase footloose and fancy-free means not committed or tied to anyone or anything, and in particular not emotionally involved with, or committed to, anyone.
The adjective footloose means free to go or do as one wishes. The formation of this word as well as its use in figurative contexts and in to turn a person footloose imply that its original sense was free from physical restraint to the feet, but this sense occurs only occasionally in recent sources as an extended use.
The adjective fancy-free means having no commitments, carefree, and in particular not emotionally involved with, or committed to, anyone.
Both those adjectives are first recorded in the 17th century, but their use in collocation is attested in the 19th century only.
The earliest occurrences of this collocation that I have found are as follows, in chronological order—in each case, the context is political:
1-: From the Republican Banner (Nashville, Tennessee) of Wednesday 20th March 1867:
The people of Tennessee hate, loathe and spurn all professional slanderers as they hate, loathe and spurn all political corruptionists, shoulderstikers, mobbists, incendiaries, confiscators, and the like. Our aim is to try and re establish [sic] civil government in our midst, and we want the aid of no extremists, North or South. We are the ally of no party hostile to the Government or the Congress. We are foot-loose and fancy-ree [sic], bound at the wrist by no entangling alliances. We shall make a plain Republican effort here for a plain Republican fabric—and we shall GO IT ALONE.
2-: From The Courier-Journal (Louisville, Kentucky) of Sunday and Monday 29th and 30th August 1869:
As we [= the Democratic Party] have no common ground to stand on, as we have no national policy to which we are irrevocably committed, as we are out of power and therefore not so nervous as we might be if we had the quartermasters and the wagons to look after, as we are foot-loose and fancy free, with the whole country to pick and choose from, we need be in no great hurry, and we can afford to speak our mind out abundantly and to whack each other roundly.
word histories 