In theory, yes. But not if they don't have php/mysql installed or available with your hosting package. So don't just buy hosting because its Linux thinking you can install wordpress without checking first..
It does not depend on the Operating System. Just simply if they have mySQL and PHP support. Apache is not even a problem if you want mod_rewrite for URL re-writing as that installs on both Windows and Linux too, but its not a requirement.
As long as your hosting package gives PHP support (nearly every single ones does now) and 1 x mySQL database, your sorted.
Good point Darren. There's databases included with openmind, think I'll plonk for them.
Hey Glen, cheers for the offer, but I'd rather go with someone with a control panel etc. and a bit more experience in it. Good you're offering hosting, but I guess it will mainly be aimed as an add-on package to other services (such as when you create a website, host if yourself)?