1) content is key. you must have original, unique content on your deep pages. this is by far the most important point which ultimately decides most of the chance that your site will get indexed fully and will get traffic or not. if you dont have enough unique content per deep page - generate it. lots of methods for doing this - translation, related pages, doubling links with anchor text, autogenerating screenshots, watermarking, generating MP3s from text, etc etc etc.
2) good site structure internal linking. every deep page must be reachable within 2-3 clicks from the root page. every deep page must link to 20+ other pages in a relevant manner (related/similar stuff, recently visited stuff from this page, etc).
3) speed. your deep pages must load FAST. if your site loads slowly, you can practically forget it from the outset - Googlebot doesnt like that and its unlikely you'll ever get much traffic from G unless you gain some astronomic PR.
4) external links. this is less important than 1 and 2 for megasites, because its not like you'll ever get backlinks pointing at even 10% of your deep pages anyway (well, there are somewhat grey-blackhattish widget tricks for doing it, but i'd keep my fingers away from that if you dont want to risk a ban). we have numerous sites with over 1 mil pages indexed which have just a few hundred backlinks in YSE and like 5 in G.
there's much more, but this is the basics.