if you can translate the old urls to the new urls using a translation table or using patterns and well-defined rules with possible exceptions, you can use mod-rewrite directives in the .htaccess file.
if the url translation requires a database lookup then you will need to internally rewrite the old urls to a script that provides the proper response.
the internal rewrite will also require some mod_rewrite code in the .htaccess file.
it will be helpful if you can distinguish old urls from new urls for this internal rewrite.
anything more specific than that requires more information about what your urls look like.