If you update to iTunes 9 and don't see the Genius Mixes (even though you have the Genius enabled), simply select Store » Update Genius.
Once the Genius update is complete, the Genius Mixes entry should show in the sidebar.
[robg adds: I had this exact issue, and dug around looking for a preference setting; it didn't seem obvious that updating the Genius would solve the problem...but it does.]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20090909151524636