Rhythmbox Pandora is a plugin which allows you to listen to Pandora, add and remove radio stations and love, ban, tired or bookmark songs. It has all the features Pithos has (except last.fm scrobbling) and it actually makes use of Pithos to integrate Pandora into Rhythmbox, but the recent versions don't require you install Pithos to use the Rhythmbox Pandora plugin.
The Pandora Rhythmbox plugin has been updated recently and it finally works with the latest Rhythmbox 0.13.3+ (available in Ubuntu 11.04, etc.).
To install Rhythmbox Pandora plugin for Rhythmbox 0.13.3, use the commands below:
sudo apt-get install git-core cd git clone https://github.com/mzheng/rhythmbox-pandora.git cd rhythmbox-pandora chmod +x setup.sh ./setup.sh
Then start Rhythmbox and enable the Pandora plugin.
For Rhythmbox 0.13.2 (available in the WebUpd8 PPA for Ubuntu 10.10), see this.
Rhythmbox Pandora plugin homepage @ Github.