There should be no need for additional applications - it is built right into the iPhone and the Apple TV. AirPlay is Apple's method of sending audio or video to another device. First, you want to go into the Settings on your AppleTV, and ensure AirPlay is enabled. Then, on your iPhone, ensire it is connected to the same wireless netwotk your AppleTV is on. Then, go into Spotify and play some music. Once the music starts playing from your phone, double tap the home button on your phone, and once the mutitasking bar comes up on the bottom, swipe once to the right. To the right of the music controls, you should see a button that looks similar to this:
(That's actually the button from iTines - I'm unable to use AirPlay on my phone at the moment, but the button looks somewhat similar.) Hit that button. You should have a choice of devices - in this case, you'll probably see "iPhone" which will be checked, and "Apple TV." Tap on the Apple TV option, and after a few seconds, your music should start playing on your Apple TV, and not your phone.
Edit: It should be noted that AirPlay was introduced in iOS 4.2, so if you've got an older version, I am not aware of any way to do it if you can't upgrade.