Make sure the SEO company has:
A proven record of growing clients
A clear process
Quality content and backlink production
Up-to-date SEO best practices
Good communication and reporting