To sentimental Victorian poets a "fairy fay" literally meant a fairy, as in John Crawford's "Doric Lays" (1850), p. 77:

"Viewless forms of fairy fay
Lilt a winsome witching lay."

James Ballantine's "Poems" (1856), p 70:

"THE WEE, RAGGIT LASSIE ...

Thy form is licht as fairy fay."

and in L. S. Bevington's "Key-Notes" (1879), p. 70:

"THE SONG-BIRD, AND THE FAIRY ...
How shall it be, my fairy fay,
       When to-morrow we greet?"

In "PWD," in the spirit of writers like Ballantine, it means a delicate, "fairy-like" woman - amusingly undercut by her "curly eyes and laughing hair."

According to James R. Fuld's meticulously researched "Book of World-Famous Music," "PWD" first appeared in the Harvard song book in its 3rd ed. of 1883. Fuld writes specifically that "The song is not in the 1880 edition at HU [Harvard University], or 1881 edition at LC [the Library of Congress]."

It's mentioned earlier, however, in the student paper "Cornell Era" of Feb. 25, 1881, in a report on the "Engineers' Banquet" held on the 21st:

"Many songs were sung, some for the first time, and some very often. Some of the new ones were, 'Rank Tank,' 'Here’s to Elocution, for she holds
us in solution,' 'Engineers’ Te Deum,' 'The Noble Duke of York,' and “Polly Wolly Doodle.'"