Airportibo - 11:50 pm on Sep 8, 2004 (gmt 0)

The more people link to your site, the more high quality links you get, the faster your new site will be indexed. The better your content, the higher the chance that people are willing to link to you. (to answer your first question)
But usually I don't wait for people to do this by themselves. So the other options are:
- put links on other websites I already have
- kindly ask other webmasters
- pay for a link(s)