Q:

What does 氏 mean after a name, how is it different from さん or 様?

If you look in the dictionary for the definition of 氏 you'll find it defined as: family name; lineage; birth.
However I have seen it used in such a way that it is doubtful that it means any of those things in certain contexts.
Here's an example sentence:
今日はマオ氏のアーバンカーで送ってもらった♪(´ε｀ )
What does 氏 mean here?
Note: Mao is a very famous Japanese singer.

A:

The list of respectful honorifics, with more respectful at the top, goes like this:

殿{どの}
氏{し} 
様{さま}
さん
チャン、くん
(not putting an honorific)

There are more, with obscurities like 刀自{とうじ}, and you can see a full list here (in Japanese).
殿{どの} means "lord", which you might use in a sense like "Lord Byron". Items 2 down to 4 can, and often are, all translated as variants of "Mr", or "Mrs/Ms".
However, this is one of those situations where the English is only a starting guide for the learner, but the translation breaks down pretty quickly. 
The first notable differences is that the Japanese is not gender specific, except for number 5, where ちゃん is usually female and 君{くん} is usually male. But not always.
Another difference is that they can be applied to first names as well, which often trips English learners of Japanese. There are giggles at the thought that someone might call you "Mr Bob", but they don't mean "Mr", it's just a respectful way of addressing someone. ボブさん is fine, so the sooner you can get away from the "Mr" correlate, the better.
(Note that it's pretty rare for a Japanese person to refer to another Japanese person by attaching さん to what English speakers would call a "first" name, but it's not because it's necessarily wrong to do so, just that it's usually it's more proper and respectful to use the family name.)
Another difference is that they aren't really used on their own. So, for example, in English, you might say to someone "Hey mister!", you wouldn't call out in Japanese 「おい、さん！」.
Okay, so, all that said, what does it imply if you use 氏{し} with someone's name instead of さん? Well, since we can throw out trying to translate it to English, we can simply say this: it's just more respectful than さん. If you look at it like that, you can't go wrong.
There are some circumstances, like work or other places, where 氏{し} might be standard as part of the keigo used. However, in the sentence in the question, it's a matter of a fan adoring a pop star. Using 氏{し} conveys that higher respect, and also smacks just a little of old-school hierarchy. It's like referring to David Bowie as something like Master Bowie, if you happened to be a fan of his.
Part of the confusion in the question is that 氏{し} also has other definitions, like "lineage" and so on. That's just a function of the kanji carrying a meaning, as kanji characters do. The kanji 様{さま} also has various meanings, like "manner, kind, appearance", but that doesn't impact that it's used as an honorific, although it might have factored into why that kanji got used in the first place. But don't take the kanji definitions too far. 様{さま} also means "mess, sorry state, plight", which are definitions that have nothing to do with its use as an honorific.
Hope that helps.

