should it cost money to publish your domain name with the search engines? is it easy to do? have you done it? why some hosting companies don't offer this service?

Some do, some don't.

Some search engines or directories have what they called paid or sponsored listings. Some don't. And it is always easy to do when you are willing to pay.

Some hosting companies do it for commissions or as gimmicks, and some don't.