Sometimes, it is necessary for a package to get a new name. Although this should rather seldom be the case, there are some situations when it makes sense, for example when the name of the upstream application changes. Of course an apt-get dist-upgrade should still seamlessly upgrade the package, best by completely removing the old package and installing the new one as a replacement.
Method 1 (only useful in very easy cases)
One method is to just have the new package provide, replace and conflict the old package. This had two disadvantages: If there are versioned depends on the old package, they will break and most package managers (including AFAIK apt) do not know to replace the old with the new one and will only do it if anything pulls in the new package.
Basically, the solution is to define a binary dummy package with the same name as the old package in the control file of the new package. The new source package takes over the binary dummy package, and the old source package, which is then binaryless, will be cleaned up by rene, an archive cleanup tool.
Assume that the last upstream version of the old package "oldPkg" was 1.5 and the package was renamed to "newPkg" for version 2.0.
Then, the dummy package is defined like this in debian/control:
Package: oldPkg Depends: newPkg Architecture: all Description: transitional dummy package
This entry defines the binary dummy package. It will get version 2.0-1 and automatically be pulled in by an apt-get dist-upgrade if an earlier version of oldPkg was already installed.
The package only installs the mandatory files in /usr/share/doc/oldPkg and possibly some compatibility symlinks, see below.
Since it depends on newPkg, it also installs the new package.
Note that the package does not contain any architecture specific files anymore and therefore the Architecture is set to "All", even if it was "Any" before.
The new package is defined like this:
Package: newPkg Replaces: oldPkg (<< 2.0-1~) Conflicts: oldPkg (<< 2.0-1~)
You can also add a Provides: entry. But that will only help for unversioned depends anyway and there is the transitional package to keep the reverse depends working.
Please make sure that you use the proper version to conflict against. You must make sure that you conflict against all versions which still have the files in the old package. Especially if you split it between two debian revisions, you must add a debian revision and not only conflict against older upstream versions. (Or you will stumble across bugs like #397993).
If your new package also changes some interfaces to users or other packages, for example the package name changed because the program name changed, you might want to add compatiblity symlinks. Those can either be placed in the old or the new package. If the symlink there there to stay, place it in the new package (so users can remove the transitional package and still have it). If the symlink is supposed to go away, placing it in the old package has the advantage that users can choose to have it or not (of couse make sure to give the old package a proper description stating that it contains that compatibility) and that there is an easy way to see which other packages still need to change (things depending on the old name may need the compatbility symlink, while things depending on the new name must call it with the new name). As packages that have been in a release will need to have the transitional package in the next release, that extra information is especially useful if the package never released so the transitional package can be removed soon or if there are chances the transition to the new name will take more than one release to have all reverse-dependencies fixed).
This page used to describe a method trying to get rid of the transitional package automatically by removing all it files. If you are intrested why this does not work at all, take a look at the history of this page.