If you have Genius Mixes created on iTunes, you will need to choose to sync them by going into the Music tab of your iPhone in iTunes, and select the Genius Mixes you would like synced under Playlists.
Oh. I appear to have been beaten to it.
Oh #2. You just had to out-do me didn't you... 😛