I just recently bought a refurbished laptop. I have seen stories of refurbished phones being sold with spyware, trojans etc installed on them. My question is, what steps should I take (outside of running a virus protection scan) before i start using the laptop to ensure there is no spyware, trojans, keylogging, etc? And this second part question may be harder (or impossible) to answer, but is there a way to be absolutely certain it's a clean laptop?
Update the motherboard firmware, manually, and reinstall the OS, reformatting the drive. It's not a complete guarantee of security, but it will get rid of 99% of the likely threats.
By "refurbished", not just "used", do you mean a proper manufacturer refurbished item? In that case your risk is somewhat lower than with a plain used item, as the manufacturer won't deliberately install malware.
There is no way to be absolutely certain. Theoretically, if you were a high value target, someone could even install a hardware chip to spy on you.
@Therac got the basics - wipe and reinstall. Hardware malware is less common but exists, so reinstalling firmware isn't crazy but may not be necessary depending on your experience/risk acceptance level.
I'm mainly just adding one note: your question implies that "new is safe" but this isn't actually true either. There have been cases of new hardware/systems coming with malware pre-installed too! Example: