"Bought it cheap" sounds worrying. Alarm bells were already ringing when you said it didn't have a Windows Licence on it anywhere. I'm pretty sure PC manufacturers can't sell full Windows based machines without a licence these days.
Depends what version of Windows. Windows 8 comes with the key in the BIOS now. I looked high and low for my key last night and ended up having to get a program to extract it out of the BIOS.