Use Playlists—Even If You Don't Play Them
A final, less-obvious source of information for Genius is your existing playlists. This actually seems to be one of the stronger components used by Genius.
When iTunes analyzes your library, it takes your existing playlists into account. The assumption is that if you've grouped songs together on your own, you're likely to think that they go well together already.
Therefore, it's a good idea to organize your library using playlists, even if you don't really plan to use them that much. This can be particularly helpful as a way to try to make sure that music that Genius doesn't know about still ends up in Genius playlists (although such songs still won't be able to serve as the source for such a Genius playlist).
Of course, playlists offer other advantages, such as being able to choose particular songs that you want to hear together or being able to choose to sync only specific playlists to devices (particularly if they have limited storage).