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.
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)