It depends on the app, but most of the time if you paid for it it is linked to the account, not the phone or one-time install. If the app is poorly coded or done precisely for one-time installations, then yeah, you'd have to pay again (these are VERY rare).
If you purchased it through Google Play, it should show there (paid version) as available for installation and not for purchase (because you already purchased it).