What is a Sandbox
At a high level such sandboxes are kernel drivers which intercept calls to APIs, and modify the results those APIs return using hooking. How an entire sandboxing solution works under the hood though, could easily fill several books.
As for difficulty, it's probably one of the harder things you could ever possibly write. Not only do you have to provide hooks for most everything the operating system kernel provides, but you have to prevent the application from accessing the memory space of other processes, you have to have a way to save the state of the changes a program makes so that the program does not realize it's running under a sandbox. You have to do all of this in Kernel mode, which effectively limits you to using C, and forces you to deal with different kinds of memory, e.g. paged pool and nonpaged pool. Oh, and you have to do all of this very fast, so that the user feels it's worthwhile to run applications inside your sandbox. 50+% performance hits won't be tolerated by most users.