How do I recover or "undelete" files that I accidentally deleted?

I've accidentally deleted some really important files on my machine, and I'm looking to find out how to recover them. Using the Trash bins "restore" isn't an option, as the files aren't there (mostly likely I wasn't paying attention and permanently deleted them from there). Is there any way that I can un-delete these files?

Before you go any further you should follow these guidelines when "un-deleting" or recovering lost files:

• (If possible) DO NOT USE the medium that you are recovering from. This is due to the fact that writing to disk may over-write the files you are trying to recover.
• Try to recover the files as soon as you can from the time of discovery that the files are missing. This will increase your chances of recovery.

There are plenty of options out there that you can use, however a very simple one is Recuva from pirifom:

Accidentally deleted an important file? Lost something important when your computer crashed? No problem! Recuva recovers files deleted from your Windows computer, Recycle Bin, digital camera card, or MP3 player. And it's free!

They even have a easy to use wizards for the non-Super User:

There's also an exhaustive set of documentation on Recuva including how to use it.