According to Microsoft if it is a local hard-drive, it will have a recycle bin, it won't if it is a network-drive or a floppy-drive (or presumably similar device e.g. SD-card).
The reference is removed, a metadata file is kept in the Recycle Bin to know the original location.
In the early days, on Windows 95 and 98 this was located in \RECYCLED. On Windows 2000 and later it was renamed to \RECYCLER. Since Windows Vista it is now a special folder called \$Recycle.Bin.
Use Process Monitor to see the I/O under the hood, put a filter on Recycle.Bin and visit it. :)
For example, when I do this:
notepad \$RECYCLE.BIN\S-1-5-21-0192837465-987654321-0123456789-1000\$EXAMPL5
Note: The long folder name is a User SID. The last folder name is a hash based on the metadata.
I get a file that contains metadata information like this:
Ö¸ÌC : \ P a t h \ T o \ S o m e \ E x a m p l e . t x t
The reason that the file path has spaces in between is because it is stored in wide byte chars, to support special characters for certain languages as well as unicode and what else. The earlier symbols are binary and contain information like the file size and permissions, as well as a pointer to the file data. In essence, it contains enough information to reconstruct the original reference...
It's sad that the Windows Internals book doesn't cover this, or else I would've had more reference. I haven't found any articles that go into detail on this, neither by Microsoft or by third party people. They probably do exist but I found it easier to go and reverse engineer the main concept...
Best Answer
The Recycle Bin is a special Windows shell folder that shows results from multiple locations. Each disk has a hidden $RECYCLE.BIN folder that contains deleted files originally from that volume. However, when you open the Recycle Bin, Windows doesn't show you only what's in that drive. Instead, you see a combined view showing all $RECYCLE.BIN folders from all mounted volumes.
You can see which disk volumes Windows will include in the Recycle Bin as follows. Simply right-click the Recycle Bin on your Desktop and click Properties:
If you wish to delete the Recycle Bin contents from your external drive, see How to delete $RECYCLE.BIN folder on external hard disk?.