Welcome to WebmasterWorld!
After the current update, Google will deep-crawl all sites that it can find links to. At the end of next month, the data that it collects during this deep crawl will be included into its results. Since you say your site's been up for "almost four weeks", it sounds like you just missed the last deep-crawl, so look for your sites to appear at the end of December.
Other search engines are a bit less predictable; If you have a lot of incoming links, some of them may pick you up a lot sooner than Google. Others are slower, though.
You can submit your site to Google, but the best way to get into Google and stay in is to get incoming links.
Submit your site to the Open Directory Project, and contact other webmasters in your subject area and ask for on-topic incoming links to your site with appropriate link text. Links from sites having high Google Page Rank will benefit you the most in Google. But the more on-topic incoming links you get, the better.