How do YubiKeys work? Are there any alternatives?
I have one, and I'd recommend them! I actually got it for free from the Yubico guys, when I was attending BSidesLondon.
Think of it as an RSA secure-key, except much smaller, cheaper and without a battery. You get (essentially) the same security, though YubiKeys have a signficantly larger keyspace than the RSA ones. They're also incredibly sturdy, and can be fully immersed in water without damage.
I know this sounds like an advert, but they really are great. Compared to carrying around a bunch of those secure-keys, they're almost unnoticeable on a keyring.
As for how they work, they validate against a cloud service that Yubico run, and provide two-factor authentication. All the server software is open-source, and they're happy for you to run your own authentication servers. It's entirely transparent.
Have a dig around on their website, there's plenty of technical info and descriptions on there.
As I understand it, Yubikey acts like a USB keyboard. You plug it in your computer, place the cursor in a form field, press the button on the Ubikey, and it sends out a text string of 44 characters to the computer like you are typing those 44 characters. The computer doesn't know the difference between you typing it or the Ubikey generating it.
A website like a Wordpress site with Ubikey plugin, or the Lastpass addon in Firefox, or any other website that has a Ubikey option, has a login form with username, password, and Ubikey password. You enter your username and password, place the cursor in the Ubikey field, then press the Ubikey button, and it enters the Ubikey password into the field.
Then the form is submitted, and the Ubikey is validated in the Ubicloud. The website checks if the entered Ubikey password is valid. The Ubikey itself does not connect to the Ubicloud. It's just a device generating a string sending it out acting like a keyboard, and it does not connect to the internet or anything except as that keyboard.
Before all this works, you need to update your account on the website to use Ubikey. That means you need to link your key to the account. That way the Ubicloud can check the generated code and validate it against your account.
The website of course needs to implement the Ubikey functionality, which is available as a free service for website owners.
If the Ubikey gets lost, you can use the normal recovery methods the website has to recover your account and disable the Ubikey. Normally this means that you get a password recovery link via email, and that link disables the Ubikey function in your account.
Disclaimer: I've been wondering how Ubikey works, I've been searching for answers, and this is what I made of it. I hope it's correct, and if it's not, correct it or give a comment - I want to know!
The other answers here don't give any real explanation. Even the Linuxjournal article doesn't explain it this way. The accepted answer gives a black-box answer - not what I was looking for when I opened this page. I hope this answer gives a better explanation and writing it made me understand the Yubikey better.
Have a look over here http://www.linuxjournal.com/magazine/yubikey-one-time-password-authentication
The following outtake is written by Drik Mekel, author of the previously linked article:
Each time you press the button on the device, it generates a one-time password and sends it to the host machine as if you had entered it on a keyboard. This password then can be used by the service to authenticate you as a user.
I suggest you read through the 5 page article (as this is to much to take over here)