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.
1
See also on [unix.se]: Are Icecat and Iceweasel different projects?.
– unor – 2015-04-18T01:39:02.0501A few points and updated info: There are a few differences not mentioned in the answers below. 1) In addition to the branding, the "Ice" products exclude 3rd party additions that aren't FOSS. Example: Iceweasel excludes things like Pocket that are merged into Firefox. 2) There are different versions of the Ice products (at least for Iceweasel, I'm not familiar with the Icecat details). The main Iceweasel versions used to be based on Firefox ESR. The Stable version still is, but the others are now based on the latest standard Firefox. – fixer1234 – 2016-03-12T00:15:47.880
BTW, the reason for the rebranding isn't copyright of the brand/logo. The Firefox source code is modified to strip out non-FOSS components and whatever other changes they make, then recompiled. So the result is not what Mozilla produced and isn't under Mozilla control or responsibility, so they don't want their logo on it.. That's the reason for the rebranding. Charles Stewart's answer indicates that for Icecat, it may just be the name/logo, but that wouldn't stop them from just making it available in their repo. – fixer1234 – 2016-03-12T00:28:19.413
@fixer1234: Perhaps you should make an answer from those two comments. – einpoklum – 2016-03-12T00:29:57.947
Charles Stewart covered the gist of the second comment. My first comment is more of a supplement than a complete answer. – fixer1234 – 2016-03-12T00:39:27.267