Are IceWeasel / IceCat just re-brandings, or are they actually different from Firefox / Thunderbird?

I think the most useful thing to start with is that the Mozilla Firefox branding is copyrighted by Mozilla, the branding is NOT under a licence that allows use of it without explicit permission and that the more ideologically pure distros didn't like that. All three cases mentioned on the Icecat page are simply re-logoed/branded versions of Firefox, done by different teams - from the Icecat webpage

The gNewSense BurningDog browser and the Debian IceWeasel browser are similarly derived from Firefox, also with the intent of being free software. Technically, however, these projects are maintained entirely independently of IceCat. (Previously, this GNU browser project was also named IceWeasel, but that proved confusing.)

Iceweasel is probably also packaged by Debian for use in their distro, as would be Burning Dog (which itself is part of a 'pure' FOSS Ubuntu spinoff). They're all Firefox code, and should work the same way as firefox, but are done by different groups of people for the sake of total FOSS compliance.

To answer the specific parts of this questions - yes they are different projects, they are just rebrandings of Firefox, Debian only has Iceweasel packages since they run the Iceweasel project, and as far as I can tell, Icecat changed its name from Iceweasel to avoid confusion and none of the spinoffs have merged. A great anology would be Centos and Redhat - exact same situation with Centos compiling redhat's packages after stripping out the branding.

EDIT: As of 2016 Iceweasel is no more, and the firefox branding is used by debian again - As per this raspberry pi stackexchange post by angussydney. Pop went the weasel I guess.

If a rebranding is an alternate distribution of software that may change

1. Text
2. Images
3. Baked-in URLs (e.g., to alternate web stores)
4. Easter eggs (usually, built-in pages)
5. Scripts, plug-ins, etc.
6. Configuration defaults

and nothing else (i.e., no changes to the "real" codebase), then

• I believe that Icecat is just a rebranding: the point of the distribution is just to remove the contested Mozilla branding and to link the browser to a GNU-acceptable web store, but as far as I know, GNU uses the Firefox codebase faithfully;
• However, Iceweasel is not just a rebranding: while the project is not really a fork, the point is to allow Debian to run their own security policy, which does involve applying their patches to the Firefox codebase and deciding whether to accept Mozilla patches. In fact it was Debian's security policy that led Mozilla to enforce its trademark and so create the need for an unbranded, DFSG-compliant Iceweasel. In the medium term, the Debian codebase tracks the Mozilla codebase, but with a substantial lag. Debian have not applied the auto-update code of Firefox to Mozilla, and I think it is not clear how they would go about that.