I am confused on Arya's Gift. I know that you select an attachment on your Stark character, but the card says you may move said attachment to another "eligible character."

My confusion comes from the card being similar to Jeyne Westerling's ability: "Kneel Jeyne Westerling to choose and stand a Stark King or Lord character." However, the Lord has to be a Stark, too.

Does the same apply for Arya's Gift, does the "eligible character" have to be a Stark?

No. In Jeyne Westerling's text, King and Lord are part of the same phrase (and, like Stark, they modify "character"). In Arya's Gift's text, both characters are referred to separately and the restrictions on each are separate (which is why "you control" is specified for both). In short, the character receiving the attachment doesn't have to be Stark.

Here's the relevant rules entry:

http://thronesdb.com/rulesreference#Qualifiers

Qualifiers
- If card text includes a qualifier followed by multiple terms, the qualifier applies to each item in the list, if it is applicable. For example, in the phrase "each unique character and location," the word "unique" applies both to "character" and to "location."

As you can see, this entry applies to Jeyne, but not to Arya's Gift.