These lines (and probably everything Ophelia sings) are little bits of old ballads familiar to Shakespeare's audience.
"Shoon" is an archaic word for "shoes," and "sandal shoon" means "sandals."
"[H]is cockle hat and staff, / And his sandal shoon" all indicate the person made the pilgrimage known as "The Way of St. James."
Pilgrim
with
Cockle Hat
and
StaffSource:
Wikipedia:
1300-1400 in fashion