You resolve which method is called based on the type, yes. I don't see that as "magic" since it's fundamental language functionality that you rely on all the time - in Haskell typeclasses are the way you do polymorphism.
If you want to implement polymorphism at all you will have to do something that's more or less equivalent (e.g. an OO virtual function table is effectively the same thing as a typeclass instance - it's just that the language forces you to bundle the data members and the virtual function table together, whereas in Haskell they're decoupled and can be used separately). Or even function overloading requires a similar "the compiler chooses which one is actually called" concept. (Of course there are purist languages that insist on e.g. using different forms of + for different-sized integers, but they're very much a minority)
If you want to implement polymorphism at all you will have to do something that's more or less equivalent (e.g. an OO virtual function table is effectively the same thing as a typeclass instance - it's just that the language forces you to bundle the data members and the virtual function table together, whereas in Haskell they're decoupled and can be used separately). Or even function overloading requires a similar "the compiler chooses which one is actually called" concept. (Of course there are purist languages that insist on e.g. using different forms of + for different-sized integers, but they're very much a minority)