My guess is crowd-sourced information, similar to how Last.fm tags their tracks. If it's not in their catalogue already, they find similar artists based on other listeners' song patterns and interests and select them that way.
It may just be me, but it does do a rather good job of picking not just related artists/genres, but even music arrangement (heavy bass or screaming chorus) and lyrical content.
Or maybe I've just been spoiled with my Genius selections ha. It is rather questionable at times, as well (goes from Cat Stevens to Regina Spektor? I can kinda see that.. kinda).