Load time verification is very expensive and not fool proof.

> Are there any OSes that verify program signatures before executing them?

**EDIT**: As pointed out in comments, such operating systems. ChromeOS for e.g.

>If so, what are these OSes? Are they specially crafted? How difficult is it to apply this kind of program verification to the everyday OSes we use?

It is fairly difficult to verify a program at loading time. Plus even if you successfully do it, once a program has been started the attacker can still give malformed input and cause havoc(buffer overflows). Having said that, there are software modules that verify their signatures at load time (Software attestation e.g.FIPS compliant OpenSSL). Having an operating system do it for each and every process is very very expensive.  

As the focus shifts towards cloud computing, you would want to ensure that you are able to run high assurance software on even untrusted systems. I would say that not a lot of research would be done on protecting the system from the software that is running on it. Instead the focus will be more on doing trusted computation even in untrusted environment. You can have a basic chain of trust like system or software attestation (refer the bottom link) if you want at load time. The important thing would be ensuring that the software isn't compromised at run-time.  

Look at this discussion: http://security.stackexchange.com/questions/143593/can-a-running-interpreted-program-cryptographically-prove-it-is-the-same-as-as-a/143595#143595