The major search engines, such as Google, will find your site, usually within 6 weeks of when you go live with your site.
Now (mid-2010) it will probably be a day or two at the very most. Get accounts on the major search engine sites (e.g. Google, Yahoo!, Bing) and follow the instructions for optimizing your site.
Read the information on your web provider's support pages carefully. Some include such services as part of your plan or you can use their service for minimal cost.
About the most expensive way to go is to subscribe to a plan separate from your web hosting company using automatic payments from your credit card. One of my clients noticed that after a few years, his charges had crept up to over $100 a month. When I investigated, he hadn't logged on to their site to configure it, so it wasn't even running!