Mark,
If you are only doing a re-design you don't need to do all of the backlinks again or any search engine submissions. However, if you are having any new content then the placement of the words on the new site is key to getting seen in the search engines.
I have designed websites for about 10 years now and have always found this tool to be quite useful;
www.ranks.nl - Keyword Density Analyser
It tells you how prominent your key phrases are on a particular page. Anything over 60% is good.
Make sure your site is using <h1>, <h2> tags etc and ideally CSS.
Sorry to sound like a nerd but if you need any help with this let me know, I can point you in the right direction at least without actually doing it for you