I've done it twice. There are a couple of different ways, but I used the "case screw" method. I've read some articles saying how easy it is, but I was gritting my teeth both times at the force I had to use. I also had one of the pins get stuck each time and ended up using a light "drift punch" and a couple of pieces of wood. Maybe it's just me (I'm not a total klutz) but I recently read an article (somewhere) where the same thing happen to some guy and he ruined his cpu. There's an article with some pictures at:
www.overclockers.com
Look for the article entitled "Removing the Heatsink from a Retail PIII."
It was worth the worry as I'm using Alpha P3125's with dual 60 mm. fans. What a cooler, although not without its caveats.
Mike