If you submit a sitemap to anyone, DO submit one to Google. It tells them that your site exists so that they can schedule a crawl. It may still take several weeks before they get around to crawling your site, but they WILL crawl it usually within a few weeks. It does not guarantee that any of your pages will be indexed, but at least they will know you exist and crawl your site. The REAL advantage to submitting sitemap.xml files to Google is that you can indicate which pages YOU feel are the highest priority to be crawled/indexed. So you get to say, "If you index any of my pages, index this one first... then index these next... if you like my site and want to index more, index these pages next... etc." Getting links from URLs on other sites that are already indexed can speed up the process of being crawled and indexed. But it's always a good idea to submit sitemap.xml files if your site is new.
Submit your sitemap to google only after you've been indexed. You want to be found naturally. Do what's been recommended and submit some articles / SB'ing ect. Your site may have been crawled already, it just hasn't been indexed yet. Give it time.