The attached PII is the one you received? Yeah, that definitely needs a HS(F). Not sure about installation though, as every Slot 1 I've bought had one attached already.

I'm wondering if you couldn't actually put in a faster CPU though. I can see the board has jumpers for CPU FREQ, which only goes up to 333MHz. But I think this is purely taking into account that the 333 MHz PII is the fastest PII you can get on a 66 MHz FSB. I'm also not sure why it needs these jumpers in the first place, as most Slot 1 or compatible CPUs are multiplier locked (with some exceptions). Mendocino Celerons are all 66MHz FSB, up to as fast as 533 MHz. I would be curious what would happen if you put one in with a slocket adapter. Can't see why it wouldn't work, except for potential OEM weirdness.

Regarding heatsinks, the thing to know is that there are three different kinds of Slot 1 package:
- SEPP (Slot 1 Celeron only)
- SECC1 (early P2 - including this CPU)
- SECC2 (later P2 and P3)

P2-333 could have either SECC1 or 2, but this pic shows it's clearly an SECC1. So you need an SECC1 HSF. They sort of clip on, using the rectangular holes you can see there. The IBM instructions you link to are correct for this SECC1. As for the heat sink fan (HSF) you've ordered, it doesn't explicitly state SECC1 or 2, but Athlon uses SECC1, so if the description is correct, it should be SECC1 and therefore suitable for your CPU.

You don't need the huge HSF of a P2-300. The difference between the hottest Klamath core and one the coolest Deschutes is significant - 43W vs 20.6W, so less than half the output. You have one cool CPU.

As for thermal paste, you want that wherever two bits of metal (or ceramic) need to interface thermally. So regardless of whether there is any on the inside of the SECC1 package, you want a dot on the outside between cartridge and heat sink. "Dot" is the relevant bit here: the role of the paste is to fill in air gaps, metal-on-metal still conducts a lot better than the paste, so only use a tiny amount. If you have a thick layer between the two, it won't work well.

I'd agree with giantenemyca; if any Celeron Mendocino will run on this board, there's a good chance they all will. There are native Slot 1 Celeron CPUs up to 433MHz and using a slocket you can go up to 533MHz (just make sure yours is black&steel Mendocino, not green&blue Coppermine). It's remotely possible but unlikely that Coppermine CPUs might work - but that would require more effort (the VRM of your motherboard can't deliver below 1.8V and will refuse to boot if a CPU asks it, so you'd need a slocket with voltage override jumpers to force it to 1.8V to even try this) - if succesful you could get as high as 766MHz.

It's true that your board only has four documented multiplier settings, but:
- with three jumpers, there are actually eight settings, which correspond to the BF0, BF1 and BF2 pins on the CPU and offer 8 settings between 2.0x and 5.5x
- Mendocino (and Coppermine) CPUs are all multiplier locked unless engineering sample. Your CPU will ignore whatever your board sets anyway. So a 533MHz Celeron will always run at 8x multiplier if it runs at all.

Clock-for-clock a Mendocino Celeron is about as fast as a Deschutes P2 (they have 1/4 of the L2 cache, but run it twice as fast), so a Celeron 533 will be about 50% faster than your P2-333.

Note that most P2-333 are actually unlocked, so you could potentially play around. You can find the full mapping of the pins at the bottom of this page:
https://pchardwarelinks.com/cpuspeed.htm