Interesting question. Ocham, Flaminius and GSantise have already explained the general rule quite well (好き is indeed a "NA" adjective-verb which takes が with its subject), but the question of why を is sometimes used remains unexplained. GSantise posts some intriguing examples, and I think is very close to the right answer with the observation that
" を operates as it usually does, i.e. to point to the object that receives the action. In this case, it seems to work because its part of what looks like a dependent clause to me (meaning you would never see "彼のことを好きなひと” totally by itself because it doesn't make a sentence)."
I just want to add a few thoughts.
For those who are new to Japanese and wondering why 好き takes が, perhaps the best way to think of it is to translate 好きだ (and its various alternatives) as "is liked" or "is preferred." In other words, in Japanese, when you say that you like something, you're not so much making a statement about yourself, as about the thing you like. The key point here is to remember that は does not indicate grammatical subject, but rather "topic": it is well (if clumsily) translated in most cases as "as for X." So, when you say,
what you're really saying is
As for me (or even "In my case"), sushi is liked (or preferred).
The grammatical subject of the sentence is not "watashi" it is "sushi." Thus, you would never use を here, since its function is to indicate the direct object of a verb, not the subject. (The same, of course, applies in a sentence with no "topic" indicated. すしが好きです means "Sushi is liked" and only context will tell by whom. However, in practice, there's rarely any ambiguity.)
That leaves, however, the interesting question of why we sometimes see (or hear) ~を好きです. Before posting, I did a simple experiment (you can try it too!) by Googling the two phrases (using "da," which is more likely to appear in writing), with "wo" and with "ga." The results are . . .
が好きだ "about 6,920,000"
を好きだ "about 593,000"
So it's about 10 to 1 in favour of "ga." But more importantly, if you try the Google test, you will see that virtually all the results (I admit, I haven't looked at all of them!) for を好きだ are actually "quotative" expressions, using the quotative particle と and some variation on 言う or 思う etc. For example, from Amazon.jp, there's the title of a book
誰がおまえを好きだと言った (Who said they liked you?)
or a pop psychology website asks (ominously)
好きな人はあなたのことを好きだと思う？ (Do you think the person you like likes you?)
And so on for as many pages as I could bother looking at. (There is one exception,the phrase を好きになる as in 自分を好きになれないとき or 人を好きになること, about which more below.)
At any rate, what's happening here, I think, is that the addition of 言う or 思う and their equivalents trumps the regular subject-complement pattern in が好きだ. In Japanese, when you call someone something you must (normally) use を. The key is that the "something" that you call someone is an objective complement (not necessarily a compliment!), and therefore "someone" must take を to indicate it as the object. That's complicated! But a few examples (also Googled) should clear it up.
君を馬鹿(baka)だといったんじゃないよ I didn't say you're an idiot!
貴方(anata)は笑顔で私を嫌いだと言う You smile and say you hate me.
And so on (note the equivalent use of "kirai da" in the second example). The pattern is
X calls Y (a) Z.
which in Japanese terms becomes
X は (が) Y を Z と言う
X は (が) Y を ばかだ と言う
X は (が) Y を 好きだ と言う
etc. So, to return to GSantise's example
is another analogous use of the quotative pattern. It could be rephrased as
There may indeed be a more elegant solution to the problem, but I think that this at least points the way towards one. The key point is that when を is used with 好きだ (or 嫌いだと etc.), it's almost always going to be a special usage in which either the expression is
1) quotative (as above)
2) in a dependent clause as GSantise suggests
But it's a complex subject, and I won't be surprised if someone can come up with counterexamples. So I'm looking forward to hearing if anyone has other ideas.
At any rate, for anyone starting out, the simple rule is: use が when talking about yourself 私はすしが好きですand を when talking about what others say or feel 彼はすしを好きだといいます.
And as for を好きになる and が好きになる, both are used with similar frequency (actually, it's about 2 to 1 in favour of "wo" according to Google) so either is probably fine in this one locution. Either way, it's almost always used attributively, and so it falls under the "dependent clause" rule.
p.s. Holynightfever, you should start a thread about "koto." I'm sure it would be very interesting.
p.p.s. Editing back (whew, this is a complicated subject!). I just realized I left out one crucial distinction in formulating my "rule" above: it applies only in the case of "indirect quotation." If you are quoting the actual words of someone, then you would still use "ga."
He said he likes Sushi.
He said, "I like Sushi."
Which raises the whole issue of direct and indirect quotation. Komatta na! In another thread, on another day, perhaps . . . Ja ne!