Skype on Linux was always a bit of a drag to install, and for some reason a 64 bits version is not available for Fedora. It is unlikely to change now that Microsoft bought the whole shop. Luckily, the old 32 bits version still works, with a few tricks.

After downloading the RPM, install with

yum install skype-2.2.0.35-fedora.i586.rpm

Get the 32 bits versions of these libraries:

yum install libv4l.i686 pulseaudio-libs.i686 alsa-plugins-pulseaudio.i686

And finally, make sure you have these binaries:

yum install ld-linux.so.2 libasound.so.2 libXv.so.1 libXss.so.1 libQtDBus.so.4 libQtGui.so.4

Thanks to drjolo and tuxor for these fixes.