Search Engine Optimization concerns?

What is the best advice that you can give to help me with SEO on my client website? They have indicated that when a person searches for their name, they would want a link to show up in the search engine that directs them to their new companies page. I am doing the basic things on the back end, creating a site map and setting up keywords/phrases. Is there anything else that the WPMU dev professionals would recommend?