Spurred on by looking at Kongoni GNU/Linux I found myself curious and decided to investigate what, if indeed there is any, the difference is between Iceweasel, which appears to have existed first, and IceCat, which until reviewing above distribution I'd never heard of. That's probably because I prefer to use the original software, or if I don't agree I use something completely different. I remember Debian which I was using in the day switching to Iceweasel because of branding and issues with patches, so what was the deal again? Enough people seem to stumble over this so hopefully we can clear up the confusion.
Iceweasel is the renamed Debian version of Firefox. During the development cycle and shortly before Debian 4.0 'Etch' was to go into freeze Mozilla asked the Debian project to review their use of the Firefox brand and logo "before you put out another long-lived release". The newly created Mozilla Corporation, as opposed to the Mozilla Foundation who had previously seemingly condoned use of the Firefox name with a different logo (Deer Park), did not like the Debian policy of backporting security patches to their old releases in the stable branch rather than upgrading Firefox to the new version, and was also of the opinion that to use the name Firefox would also require the use of the trademarked icon and logo (see bugreport opened by Mozilla, status: serious). To do otherwise was deemed a trademark violation. In addition Mozilla asked, if Debian retained the Firefox brand, for all patches to be run by and authorised by Mozilla, as Debian specific patches would alter the code of the product Mozilla had originally released. Essentially a Firefox 2 in Debian would have been around a lot longer than the Firefox 2 released by Mozilla, with its code more and more removed from the original Firefox 2. If this product had retained its name and logo Mozilla would have still remained associated with it, but it seems feared they had little influence on Debian development. Basically they feared that patches they had no control over might be buggy or alter the browsers behavior and they would be blamed while having no influence on it.
In addition, and prior to this, the Mozilla trademark policy had already been discussed within the Debian project (in 2004 and 2005) as the logo did not meet the DFSG (Debian Free Software Guidelines). Because the logo was trademarked it was not considered free and could not be included in the Debian distribution. These irreconcilable differences led to Debian re-branding the browser and creating Iceweasel so as to make sure no-one could mistake it for Firefox. The browser has also been used by other distributions like Zenwalk, but mainly appears in Debian and derivatives. It left Debian free to patch and adapt it to the needs of their distribution.
So, contrary to general wisdom, Iceweasel is not just a re-branded Firefox, and although it should work just like Firefox, in normal operation as with extensions, it sometimes doesn't and seems to introduce its own bugs. It also seems to fall behind in patching lately as maintaining it is a one man's volunteer effort.
Similarly Icedove was created to replace Thunderbird, Iceape to replace Seamonkey (formerly the Mozilla suite) and Iceowl replaced the Sunbird calendaring application. There are other Firefox clones like Burning Dog.
Now it's getting really complicated. Apparently at the time the Debian project needed a new name an entirely 'free software' re-branded version of Firefox already existed. It was done by the GNU project and was called IceWeasel but has since been renamed to IceCat. The GNU website describes it as the 'ethical choice' as it strips out all reliance on and reference to non-free software, trademarks and plug-ins and add-ons. The crash reporter Talkback in previous versions of Firefox and Mozilla was also considered non-free software and as such removed. The GNU project operates its own free plugin finder and maintains a list of free plug-ins and add-ons instead. Similarly GNUzilla is the 'free software' answer to the Seamonkey/Mozilla-suite. In addition, GNU IceCat and GNUzilla have introduced additional security features and provide warnings against URL redirection, a method where sites rewrite the host name in links redirecting the user to another site, mainly to "spy" on clicks.
So, both Iceweasel and IceCat are a separately maintained, unrelated rebranding of Firefox. IceCat seems to take it further to the point where it could be considered a fork and seems more actively maintained nowadays. I speculate this is why it is becoming more popular. None of them are "exactly like Firefox, just with a different icon". Ditto for the other replacements.
To add to the confusion there is also Swiftfox, whose aim it is to provide an optimized build of Firefox for both AMD and Intel processors separately. The current build is 3.6.8 as is Firefox, but it is not always that up to date.
Icefox tries to do the same for Debian but seems stuck at 3.5.6, with the last developer entry from January 2010.
After all this I'm beginning to feel like the little dragon in the icon at the top. Think I'll go and use Opera from now on.