The first step of all is:
- working website, no dead links (ie. that error)
- website up 24/7, able to cope with traffic
- "basic" robots.txt, blocking access to sections
you dont want indexed.
Before you start actually PAYING for inclusion you should exhaust the free directories (most notably, the Open Directory Project, I think Google & Altavista still offer a free submit).
After that, invest in Yahoo, they can generate quite some traffic, if you are in the right category, no idea about the other ones.
And then its optimise till you drop.. :)