I actually looked all this up a month or so back. I recieved a star in my name as a gift 2 years ago, and recenlty a friend wanted a cool gift for his wife so I suggested it. As I searched for the site that mine may have come from I stumbled upon som reviews about actually buying stars etc.
basically these companies, International Star Registry, have a list of stars that NASA has documented. The COMPANY will name a star for you, but its not like NASA or any other science company/program will ever use the name you choose to identify your star. Its basically one of those 'oh the its the thought that counts' kind of gifts ...
Better said here:
Wired News: Buy a Star, But It's Not Yours
"The star names sold by the International Star Registry are not recognized by any professional astronomical organization."
The International Astronomical Union is the only scientific body authorized to name astronomical bodies.
"We produce a good product, a fun product. We may have planted a seed with people, educated them even slightly about astronomy, about the stars," said Rocky Mosele, vice president of marketing and advertising for ISR. "For people to say, 'Well, it's not official' -- I think people are OK that it's not official. I'm sure of it. I know because customers call again and again and again."
EDIT: here is another helpful site;
Interesting information about Star Registry companies