I do it all by ear, and honestly a lot of my "interpretation" just comes from being sloppy in this process. As long as it's recognizable, I don't really worry about whether I've got all the exact same notes and chords as the original. That's a lot of the fun of arrangement anyway: those moments where you go "that doesn't sound quite like the original..... but actually, I kind of like it, so let's roll with it"
As for how to come up with arrangement ideas, every mix I do starts out as a rhythm guitar part. I figure out some chords that sound close enough, then mess around with it. Try it faster, try it slower, try it with swing, try it in a different time signature, try messing around with the chords and see if I can still hum the melody over them, try switching everything to minor if it was major and major if it was minor, etc. Then once I find a style I like, I build back up from there.