Let's start with the difference between crawling and indexing. I've never seen a site of any size that was 100% indexed - but googlebot will often check out (crawl) all or almost all the URLs. Then they have an algorithmic approach to what will and won't be kept in the live index.
I'd say, in addition to getting those 301 redirects implemented ASAP, the best step you can take is an XML Sitemap. And watch your Webmaster Tools reports like a hawk for signs of any technical errors - fixing them as fast as you can.
I should have been more clear on my wants/needs. Obviously no one gets their entire site indexed (unless it's around 5 pages), but what I meant was, what's the best way to get the most possible pages indexed (besides common methods like a sitemap) after something like the botched 301 situation I explained?
I used to have decent rankings but now am starting from scratch...
Get those 301s in place - you'll see some rankings reappear soon enough, as long as the newly developed site isn't full of technical problems.
And I assume you've got good internal link structure for the new site. That's a big deal. Then even more, getting some backlinks changed from the old URLs to the new ones is also a good step, even if tedious.
One thing I'm not clear about. You called this a site "migration". Are you now using a different domain name?
I agree with Tedster, get those 301s in place ASAP. I would also take a look at Google Webmaster Tools' data, like the crawl errors, to see which ones you might want to fix first.
Yes, the domain is completely different but we kept the same URL structure. Would have been fine had the 301s been implemented right away but they weren't done properly so we lost most of our rankings.
The inbound links are going to be a problem as well since they are all pointed at the old domain. I know link-juice will be passed, but not all of it; I'm working on a link-building campaign now, which raises another question: How aggressive do you think is safe? As in, I don't want to get sandboxed for building a lot of links right away...
Get the redirects in place. Make sure that all requests for old URLs whether for canonical or non-canonical versions are redirected to the new canonical URL in a single step. Ensure there are no redirection chains invoked for any request.
Check out these two threads:
Advice on moving a site to a different domain [webmasterworld.com]
Moving to a New Domain - Official Advice from Google [webmasterworld.com]
They're both available in the Hot Topics area [webmasterworld.com], which is always pinned to the top of this forum's index page.