This is a rather curious idea, as noted long ago in Antoine de Saint Exupéry's The Little Prince. Even if you desire only the novel symbolism of ``buying'' a star, surely there are more satisfying alternatives --- say, planting a tree in someone's name, or giving money to a charitable cause. On top of this, the people doing the selling have no legal right to sell actual star names! If you read their fine print, you will discover that what you are really buying is an entry in a book with no official standing whatsoever. In fact, the International Astronomical Union is the only organization with the legal authority to name celestial objects, and they do not sell naming rights to anyone.
If the above does not dissuade you, see the Yahoo list of companies in this racket. The most prominent seems to be (and I hesitate even to include the link) International Star Registry. One is led to wonder if all these companies cooperate among each other to make sure the same star isn't named twice for different customers --- unlikely, given the Globe article below. And to repeat, the records they keep are not shared with, and most certainly not accepted by the professional astronomical community.
For more information on this topic, I highly recommend the following: