It depends on the filesystem. If you're using a non-jounralled filesystem like vfat or ext2 then there is some hope (and there even exists a nice ext2 undelete program). If you're using ext3, because of the way the jourmal works (zeros out the inode entry), you're more or less out of luck. The data may still be on the disk blocks, so it's possible that some non-OS dependent disk scanning tools could find it, but it's going to be hit and miss. If the data is critical, a professional disk recovery firm would probably be happy to help, but it will cost you.
Remember, in Linux, rm means rm.
[edit to add]
If you're using ReiserFS, there may be some hope, as expressed by this howto
. I've never tried anything like it, though, so I can't vouch for any of the info.