Generally how long does it take before one's site will show up in the search engine rankings?

I submitted my site about 4 weeks ago and still have not found any mention of it on any of the major search engines.

Is there any online service that will check various engines for your link to be listed somewhere within them?