So far, based on my own experience, it only took about 4-5 days, that is, if you submit a sitemap, place your links on high traffic site and have decent amount of content on your website.
I got my site indexed with in 48 hrs and intially 10-15 pages got indexed and gradually it covers most of the pages but yes for ranking it takes couple of months
A couple of days for each of my sites. In my opinion its good to get a holding page live whilst developing your site - this allows you to get indexed whilst developing (providing you build a few links). Digital Point Forums are a great place to get started in this process.
Submit some posts to social bookmarking sites and it can take a matter of minutes. Trust me I have done it.
The longest it took was 3 weeks, the fastest was a couple of days. Page Rank takes time to build up but usually it's fairly easy to get indexed
Have had it happen within 24 hours (no Google Tools), have also seen it take much longer, 3months plus.
I just built a new blog, it has 2 posts and i got it indexed within 24 hours, social bookmarking really helps to get indexed quickly