For your main question, if you want to behave according to HTTP spec, for any url that you can map 1-to-1 you should redirect using status code of 301 Moved Permanently.
For other urls, if you have the option of parsing the original url, generating and redirecting the user to a search page that has list of relevant pages you should use 300 Multiple Choices. (but I would say you are also safe to just 301 here).
Another important thing to do specially regarding search engines,
make sure you have registered for webmaster tools for the ones you care about, after you have your redirect setup, remove the old site from index and force a crawl on your new site. some even give you the option of changing the your address
https://support.google.com/webmasters/answer/83106?hl=en
another option that might take some effort but would prevent almost any broken links is to create a mapping db during migration. the db would map from vanilla thread ID to the new discourse thread ID. point your old domain to a simple server that dynamically generates the new url and does a 301 to it.
*Pro Tip: the slugs in the urls don’t actually mean anything all discourse cares about it the ID at the end.
eg. you can point to this thread using https://meta.discourse.org/t/21657
hope it helps.