I just switched to a new device and OnSong wants to charge me again. That's not fair, is it?
Nope, it's not. It's just happening because the App Store doesn't have your purchase history loaded. If you've just switched to a new device, go into the App Store and download a free app. This will cause the App Store to prompt you to sign into the App Store. Once you're signed in you can view OnSong and should see a download icon to install for free. All App Store purchases are recorded on your Apple ID so as long as you have using the same Apple ID, you can install OnSong on any device that you own.