In addition there are a lot of commercial and non-commercial data/file recovery programs out there, some of which have versions for Linux too, not just Windows (though it seems Windows is more usual OS for those apps). They might or might not work, but writing files to the disk does increase the possibility of overwriting the data you are trying to restore, so try not to do that. You could even make a 1-to-1 copy of the partition/disk with dd and work with that copy if you wanted; that way the original wouldn't get accidentally overwritten.
When a file is "removed", it is just unlinked - the data is not removed, but the file name in the filesystem is simply unlinked from the data portion, meaning that the data is sort of "marked free" - when something is written to disk, it can be written there if needed. Actually there is no way to "remove" data, just write on it - though somebody might consider it "removing" if one writes for example zeros over the data. And there are programs like shred*that overwrite certain files, partitions or even disks as many times as the user wants (for example 15) to make sure that the original data would be as difficult to fetch as possible, or even impossible. Though journalling filesystems, like ext3, make the use of such programs usually nonsense, because of the journalling - instead of files programs like shred can still work with whole partitions, because then the data doesn't depend on a filesystem's way to represent it.
So in short, try searching the web for programs that claim they can restore deleted files. That's probably the best bet..and if the data is really valuable (as in you're ready to pay to get it back, possibly a lot), then you can take the disk to a company that has big equipment for restoring data - for example suitable lab for opening the harddisk without damaging it and working directly on the disks inside rather than trough the disk's own connectors and read head. Some of such companies say they can restore data even in very bad cases, but of course it costs money.
If people remembered to take backups, this all wouldn't matter. Most people just don't bother.