En mi opinion, primero debes estar en
http://dmoz.org. Esa inscripcion es manual.
Despues te inscribes en GOOGLE. Yo uso el servicio gratuito de Add Me en
http://www.addme.com que tambien me permite registrarme en otros menos conocidos y no tengo quejas de ninguno de mis clientes. Tambien he probado el servicio que tiene
http://desarrolloweb.com pero no he tenido ocasion de hacerle seguimiento para ver que tal va.
En España, entiendo que WANADOO, IESPANA y TERRA tienen buscadores propios. Seria bueno que alli tambien inscriban manualmente tu website.