Google sitemaps are also a must.
They basically inform google of all your pages and hotwire the spidering process, you can even set how important each page is.
They're getting easier to make to:
For a static site you could do one in notepad, for a dynamic site there are scripts for generating them on the fly.
You can even use an RSS feed now.
Check it out:
https://www.google.com/webmasters/sitemaps/login