Detect if the user came to a dynamic URL and send out a 301 redirect to the new URL's. Also any time you make a big URL change there will be some down time. It will take Google a while to figure things out.

Detect if the user came to a dynamic URL and send out a 301 redirect to the new URL's

i am unable to understand this part?

It sounds like doing the rewrites has created a duplicate content problem. I.e. search engines now see two pages with identical information. A 301 redirect specifically tells the search engine robot (or a user!) that goes to the old url to head to the new, prettier URL. Did you have a programmer do the mod_rewrite? If so they may understand what is meant by a 301 from all old urls to all new urls and be able to do that for you. See:
301 redirect [webmasterworld.com]
For a forum with lots of posts this may be difficult, i.e. the programmer may have to create a script which queries the database, and creates a .htaccess file which redirects the old posts (i.e. using their post id) to the new post urls (i.e. using their titles). Or you could just redirect your more popular pages by hand.

Redirect A to B with an external 301 redirect. Requests for A are redirected to B and the URL seen also changes in the browser.

Rewrite internally from B to A so that requests for B result in A being silently served. The user continues to see only B in the browser.

Once you do this, the redirected URLs will continue to show as Supplemental Results for a year. That is the way it works, and there is nothing you can do about it; nor should you. If your "old" URLs still appear in the SERPs your redirect will get the user to the correct content anyway.

You'll have Duplicate Content issues until you get the additional redirects sorted out. Don't panic about Supplemental Results for redirected URLs; they will sort themselves out in time.