You don't need to submit to Search Engines at all. They are crawler based and submitting manually to SE won't help. You just have to submit to directories and SE will take your webpages from the directories. Make your internal navigation strong and do emphasize on creating sitemap if you don't have one.
Spiders follow links. As long as there is a crawled link to you page, be it internal if you've already been spidered, or external, the spider will get there. Now there's nothing wrong with getting an external link to a specific page either. That might get your page crawled quicker than waiting for a deep crawl. We've all seen sites where an internal page has a higher PR than the home page. It just has more or better links pointed at it.
I don't either ... remember, Google Sitemaps will not get more pages indexed than if you weren't using it. It is just an aid to give google a smarter crawl by specifying which pages you want Google to focus more on. Of course, whether those pages are actually crawled and indexed is dependant upon your pagerank and lots of other factors.