You are correct that re-licensing virtually always requires the permission of the copyright holder. This was a rather exceptional case. All material on Wikipedia used to be under the license GFDL v1.2, or any later version published by the Free Software Foundation.
The next version released by the FSF, GFDL v1.3, contained a provision that allowed any licensed material included on a wiki (below, "MMC" material on an "MMC site") posted prior to November 1, 2008 to be re-licenced under CC-BY-SA 3.0 by the wiki operators:
An MMC is "eligible for relicensing" if it is licensed under this License, and if all works that were first published under this License somewhere other than this MMC, and subsequently incorporated in whole or in part into the MMC, (1) had no cover texts or invariant sections, and (2) were thus incorporated prior to November 1, 2008.
The operator of an MMC Site may republish an MMC contained in the site under CC-BY-SA on the same site at any time before August 1, 2009, provided the MMC is eligible for relicensing.
Why on earth did they do that? Largely, this was done exactly so that sites like Wikipedia could relicense their content to CC-BY-SA, because they felt that the GFDL presented practical difficulties (e.g., requiring a copy of the full license text any time part of an article was reproduced). The FSF explains their decision in the GFDL 1.3 FAQ:
What is the rationale behind these changes?
Section 11 has been added to allow wikis like Wikipedia to use FDL-covered works under the terms of CC-BY-SA 3.0 if they choose to do so. They have told us that they would like to explore this option, and adding this provision gives them a clear path to do so.
Normally, these sorts of licensing decisions can and should be handled by the copyright holder(s) of a particular work. However, because Wikipedia has many copyright holders, the project needed some alternative way to accomplish this, and we've worked with them to provide that.
The clause allowing this has expired, because the license text explicitly only allowed it until August 1, 2009.
Occasionally, projects have unilaterally relicensed without permission form all copyright holders, including Mozilla Firefox, but this appears to simply be prima facie illegal. In those cases, the projects (1) worked very hard to contact all contributors, and (2) did not encounter any active refusals to the change from contributors (or else removed any parts from contributors who did refuse). After a thorough effort to contact everyone, they proceeded with the change, possibly armed with some obscure legal principles or possibly with the belief that any legal fallout would small enough to be manageable.
