The desktop version of the iTunes Store has had Genius recommendations for quite some time, but the feature has been missing from the iPhone/iPod touch version of the Store -- until now. Tapping on the "More" tab at the bottom of the iTunes Store app will reveal the usual options, with a new option for Genius recommendations.
Just like on the desktop version, you'll be able to view recommendations for music, movies, and TV shows based on your purchase history. You can preview recommendations and rate them "thumbs up" or "thumbs down." Results for music recommendations can be filtered to show songs or albums, and you can also filter results by genre.
Just like the recent introduction of