The feature is essentially a way to get you to buy more music you like. It uses "the cloud" to make suggestions on other artists and songs. You click on a song, and see other songs in the Genius sidebar. Or, you can click the Genius button to create a playlist of similar songs you already own.
Genius would be really cool if it actually did what Pandora does, which is analyze a lot of metadata about a song such as beat, vocals, instrumentation, and sub-genre. But it seems so much like a tool to get you to buy music, has so little actual Web 2.0 integration (if any), and - by the way - doesn't really work too well for playlists. It's one of the more lame new features in iTunes that I've seen since the 80s playlist generator.
I tested it with many of the 444 CDs I own. At first, Genius just gave me an error that it could not connect. For a few obscure artists, like Pontiak, it did not work at all. For some, the results were not too accurate: for Eisley (female fronted pop rock), it added in a band called Rocket Summer (very emo). I'm not hearing it. Curious, I tested Eisley on Pandora and Rocket Summer never came up. I'm not sure why Genius thinks they are similar.
I suspect iTunes 8 works better for finding bands similar to more mainstream artists - Coldplay is akin to Keane sort of thing. I don't have too much of that music, and I suspect people looking for recommendations are those who listen to more obscure artists.
In iTunes, a dialog box for Genius says the more people who use the Genius feature, the more accurate it will be. I'll keep checking to see if anyone else listens to Pontiak and post another follow-up. Er, eventually.