They take a hash of every X MB of your data before upload. If the hash already exists, then they don't upload it. You just get added to the access list for that particular chunk along with the others who have uploaded it.
That can't be the whole story. If Megaupload gives you access to the ciphertext encrypted with a key that neither you nor Megaupload has access to, that is useless.
