Where do deleted files go in Ubuntu?

Basically when you delete a file ("empty the trash") the index entry to the file is deleted, but the file information is not scrubbed off the disk. As explained in this Ubuntu wiki page:

This is because in Unix file systems, files are indexed by a number, called the inode, and each inode has several attributes associated with it, like permissions, name, etc. When you delete a file, what really happens is the inode is unlinked from the filename, but if some other program is using the file, it still has a link open to the OS, and will continue to be updated. A file is not really deleted until all links have been removed (even then, the data is still on the disk, but not indexed in anyway and thus very hard to recover).