If you accidentally delete something on a Mac

My recommendations:

1. Turn off the Mac immediately.
   
2. Ask yourself how much you want that file back. If the answer is several thousand dollars, send it to a professional data recovery service. (The only one I can recommend is OnTrack.) You will need to remove the offending drive.
3. If its not worth that much money and trouble, get some data recovery software on a bootable CD to run on the machine. I recommend the commercial Data Rescue II, which will let you recover one file under 5 megs with the unregistered version. The software requires an external data source (like a USB drive) and my experiences with the software were mixed, as were a MacWorld article on the software. However, Data Rescue II is made by the same company that makes the excellent Drive Genius software so it might just be that data recovery on Mac drives formatted with HFS is just difficult.
4. My tests with commercial recovery software StellarPhoenix also lacked good results and the software doesn't come on a bootable CD, which may make recovery more difficult.

Related: Free software that does this on Windows

Update: I found some free, cross platform, and open source software that does this: TestDisk. For recovering media files: Photorec.