If I'm a trusted user in the web-of-trust but my private key gets stolen by Eve, how would other users find out that my key is compromised and thus cannot be trusted anymore? Is there a way for them to find out and revoke the key?
You can publish the revocation certificate. Ideally, you should've generated a revocation certificate while you generated the key pair, so that you can still revoke even if you later lose access to the private key. If not, you can generate the revocation certificate as long as you have access to the private key.
When you publish a revocation certificate, your users have to download the revocation certificate before they'd notice that your key should no longer be trusted. They can do this by syncing their keyring with the key server where you've published your revocation certificate.