If you're doing a site redesign, then I highly suggest that you keep the same URLs after a site if at all possible. You can rewrite the new URLs so that they conform to the old URLs using mod rewrite or isapi rewrite. This will allow you to maintain your current search engine rankings while benefitting from a page "update" (the search engines like new, fresh, updated content on your site).
If you must use completely new URLs on your site, then you'll need to redirect the old URls to the new ones using a 301 Permanent Redirect.
Also, check the backlinks going to the interior pages of your site and try to get those updated, as well. If another site links to one of your old pages, then you'll want to contact them and ask them to change the link.