Moving Parallels to a new MAC

Shortly I will be in the process of moving all my data and applications to a new MAC. I'm looking for some comments on the best way to move the Parallels application to the new machine. (I know how to move the VMs, thats not an issue)

I will of course remove Parallels from the old MAC, I'm not entitled to, nor do I want, two copies.

I started with with Parallels 2.5 on OSX 10.4, upgraded to Parallels 3, then to Parallels 4, now running on OSX 10.5.

So is the best approach on the new Mac (which will have OSX 10.6) to start over again and install Parallels 2.5, apply the activation key, and then apply the upgrades? If I remember correctly Parallels 2.5 may not even run on OSX 10.6.

Or is there a better way?