App features aside, elephants are associated with memory in some cultures. Evernote likely chose an elephant for this association. PostgreSQL has Slonik as its mascot for the same reason.

https://wiki.postgresql.org/wiki/Logo#Why_elephant.3F