explorer.exe is the file in windows that manages most of the GUI desktop and windowing functionality, so without it your pretty much stuffed as you've probably discovered. While not impossible to use the computer without it, it sure as heck taxes your knowledge of keyboard short-cuts after all the usual buttons have vanished...
Have you been playing with OS start-up options? If not, has anyone else who has access to the computer been playing with said options?
If the answer to both questions is no, it's most likely the issue has been caused by a Virus, and I'd suggest you start again with a fresh install. Yes, I know it's a royal PITA, but if explorer.exe was taken out by a Virus, it's likely further damage to the OS has occured, possible including invisible, newly added security holes (as if there weren't enough in the OS already)
If you have been playing with your OS start-up settings, tut tut, you broke it
If someone else did it, do yourself a favour and down-grade their admin privileges such that they can't break something again by playing with stuff they don't know about
Now, if you have played with start-up options, I'll have to make assumptions that they are the same as under XP. While I have used Vista, it never lasted long enough to let me look at start-up options to speed stuff up. I was too busy going though the back-end stuff trying to get some stability into it and prevent the blue screens of death
Anyhow, assuming all the start-up stuff is the same as under XP, with explorer.exe running;
Click the windows button
Click run
Type "msconfig" into the option box and tap enter
Go into the start-up services tab
Check that explorer.exe is listed to run at start-up.
Check all the other tabs to ensure explorer.exe is set to run all the time also
If you needed to change anything as it wasn't set to run, click one the apply and exit
Click away the notification of changes taking affect after re-start
Re-start the computer
It *should* be fixed. If you have explorer.exe set to run all the time, get back to us. Likewise, if explorer.exe wasn't set to run and it does not run after the re-boot following the settings change, confirm the settings change was applied and, get back to us either way. It's possible if the setting is un-doing itself that a Virus is behind it, and that's a re-install job. If explorer.exe is set to run, there is something else going on and I'll have to boot under XP to try jog my memory as to where else you can edit start-up options, or other locations in msconfig where it can be turned off, all be it in a way that isn't obvious to the passing eye.
Thinking about it, registry errors may be causing it also... Maybe try running something like Abexo free registry scanner if you can. Abexo can do damage (like any registry scanner) so always back the computer up before you run it
for what it's worth though, I'm also a Linux fan. I used to be a Windows power-user that wouldn't switch to anything else, but Microsoft alienated me with Vista, and as a result I found something that IMO is better, Linux Ubuntu. Will I ever switch back? Well, that will depend on if Windows 7 is any good. I'm not holding my breath however, I'd got used to everything just working under Linux, rather than needing optimising to get the best out of the OS as under Windows typically...
All the best, and hope that helped
Rabbut