Where you host your site and how you host, depends on what you want to do with your business. If you want to give users the ability to log in, and have shopping carts, etc... you will need hosting that gives you a server side language(php, asp, asp.net, Coldfusion, ruby, JSP, etc...)
If you just want to keep it simple(for the most part) and just have static pages with links to paypal(this will be by far the cheapest route), then you'll find that hosting prices are relatively the same. As long as it isn't too expensive for your budget, I would find all of the web hosting companies that satisfy your needs first, then look at price. After all, if you don't have a problem with $7.95/month, then why would you look for something cheaper?
As far as the search engines go, thats something that you have to do yourself(but I can help if you want). Getting listed with search engines happens 1 of 2 ways:
1.) You pay nothing, and you work hard to fight to the top of their list
2.) You pay them, and you still have to fight to get to the top of the list, but you don't have to fight as hard.
some hosting companies:
<-- very popular
<-- probably one of the cheapest
<-- big hosting company
<-- very user friendly
<-- my favorite
<-- pc magazine pick
Hope that helps.
Also, if you were thinking of homestead because of their sales pitch about getting you listed on all these sites, keep in mind that it's not free, in fact it can be as little as 24.9 a month, and as much as 269.99 a month. Google has advertising programs that are far cheaper, and easier to implement.
P.M. me if you want help with search engine optimization or advertising with search engines.