I guess if you manually manage music the Genius feature will not show up (for me at least) so here's what I did:
In iTunes, click on a song and then the Genius button.
Click on "Save Playlist" at the top of the list of songs. This will create a playlist in your "playlists" section of iTunes.
Drag the newly created playlist up to your iPhone. It'll create a Genius playlist on your iPhone but more importantly the Genius function now appears to work on the iPhone itself.
Thanks to the Apple Discussion Forums.
