we have been trying to advertise our fan page using their ads, i.e. the completely crazy idea to pay facebook to drive users to facebook :) It seems that it works. People becomes fans (they click "like" button) and post to the page. Some of their friends seem to join, too. We have seen few sales but they were very little. I believe it is all about engagement there. If you can keep the people entertained or solve their problems you should find success.
As far as buying ads directly to the site - did not try that yet.
We're testing 2 facebook ads right now- one to drive users to become fans, and one to drive them directly to our website. I have a feeling I know which one will win, but they've only been up for a week or so.