Was the old phone also an Android? Are you using the same market account?

If it's the same OS, i.e. if your old phone was an Android, I'd say that you probably don't have to. Unfortunately I'm not experienced with the process of buying and downloading games onto phones, so I don't know how you'd use your old purchase.

Depends on where you got World of Goo from, really. Android Market? Humble Bundle?

I had an Android, and they both are even same brand (HTC). I have used the same gmail account on both, and it was purchased from the Android Market (but at that time was the Marketplace, now it's referred to as "Google Play")

You should be able to download it again then. Just log into Google Play on your new phone with the same account you used to buy it on your previous phone, then go to the World of Goo page and press download.

If this doesn't work, try contacting Google personally and tell them how you bought the game on the market before it became Play.