EDIT: The senario in the posts above sound more likely. The exact text of the help is "No usable encryption keys ever leave the client computers (with the exception of RSA public keys)." So they probably store an encrypted version of the keys server side.
According to Ars, the public sharing works by bundling the encryption key with the link to the data [1]. I don't have reliable access to the site, so I don't want to speculate too much, but I suppose there must be a way to export your keys so you can view your files from different computers.
I agree with the sentiment, though, that this is security theater. It's subject to the same problem as Hushmail, where they could be forced to snoop on their customers by modifying client code.
Ok, just my guess, not sure if that's what they do.
They can store the encrypted key on their server and send the encrypted key to the client whenever the client requests it. The client decrypts the key locally and use the decrypted key to decrypt the data.
With this scheme, the user can use a client on any machine to download his encrypted key and use it locally.
[1] https://mega.co.nz/#help_security
EDIT: The senario in the posts above sound more likely. The exact text of the help is "No usable encryption keys ever leave the client computers (with the exception of RSA public keys)." So they probably store an encrypted version of the keys server side.