Pandora iPhone app works with AirTunes if your iOS version is new enough
Yes, Pandora (the app on the iPhone) works with AirTunes. I just did it earlier today with my regular free Pandora login. No computer needed; just the iPhone, and the AirTunes box hooked to the stereo system. There's no longer any need for the VPN stuff or other odd workarounds mentioned in older comments.
When you play a Pandora station, choose "Now Playing."
On the bottom, underneath the thumbs down/up and nav buttons, there's a volume slider. Directly to the right of that volume slider is an icon. That's the AirTunes icon. It's small and easy to overlook.
Press it and you can select your AirTunes speakers. Great!
(The iPhone has to be in WiFi mode on the same network of course.)
I noticed something interesting. I tried a few other apps, like a piano keyboard and a synthesizer, and they were all going through AirTunes, too! Then I played a YouTube video, and it was going through AirTunes as well!
So it's apparent that AirTunes support is through the iPhone operating system, rather than Pandora itself. I'm running 4.2.1 on an iPhone 3GS. To check your OS version number, go to Settings>General>About and look at Version.