Use thermal grease for the Alpha. It'll probably come with a little package, if not you can get some at Radio Shack. Just a very thin layer on the CPU slug, then clamp the Alpha on.
For the GF Ultra, the HS is probably either screwed on, glued on with thermal epoxy, or held in place with rubber posts (like my Prophet II). If its screwed on or held with posts, I'd just use a dab of thermal grease again and attach the new HS/fan on the same way the old one came off. If it's glued on, then you may have to either get some thermal epoxy, which isn't a great heat transfer medium, or figure out some way to jerry-rig the HS/fan to mount onto the board. Nylon ties work well for this kind of thing. Again, like the CPU, what you're looking for is a thin layer of grease and tight, uniform contact between the slug and the HS.
In general, I don't find the GF2 cores get that hot, so the stock HS/fan may be fine. You don't really benefit that much from OCing the core since it's so bandwidth limited by the memory. It's the memory speed that counts, even with the Ultras.