Pandora is not complicated at all. You type in an artist, song, genre, etc. and the search field starts to predict what you want based on the letters you type - this is called auto-complete, not new but very useful and quickly becoming part of users' mental model, it's what they expect when they search. After you find what you want (e.g. Shoegaze, Mickey Mouse), the station populates your list of current stations on the screen and a song start playing right away. The process is very intuitive and few steps are required for the user to start a new station.
But the most useful part about creating a station is how Pandora explains the feature when you click into the search field. This is called feature highlighting, a contextual way to explain how to use certain areas of the product. When you click in the search field, you understand the value of the feature.
Rdio (left) has an even more elaborate way to do this called a Feature Tour (highlighting various parts of the UI upon first use). Although users can read and close these highlighted features, they have a way to open them again (under the Settings or Help menu).
All web applications, even those outside of the music space, should take advantage of this quick, low-cost, unobtrusive way to promote the value of new or existing features.