Old English næfre "never," compound of ne "not, no" (from PIE root *ne- "not") + æfre "ever" (see ever). Early used as an emphatic form of not (as still in never mind). Old English, unlike its modern descendant, had the useful custom of attaching ne to words to create their negatives, as in nabban for na habban "not to have."
Italian giammai, French jamais, Spanish jamas are from Latin iam "already" + magis "more;" thus literally "at any time, ever," originally with a negative, but this has been so thoroughly absorbed in sense as to be formally omitted.
Phrase never say die "don't despair" is from 1818. Never Never Land is first attested in Australia as a name for the uninhabited northern part of Queensland (1884), perhaps so called because anyone who had gone there once never wished to return. Meaning "imaginary, illusory or utopian place" first attested 1900 in American English.