Well the first step should definitely be to backup your website in case that anything goes wrong!
The easiest method would probably be to just open the Upgrade page in JoomSEF and enter the 3.6.3 package and let JoomSEF to upgrade automatically.
If you really want to do the uninstall/install, you should export your current SEF URLs to a file and backup your JoomSEF configuration file /administrator/components/com_sef/configuration.php. Then uninstall old version, install new version and import your SEF URLs and copy back the configuration file. Then you need to install all your JoomSEF extensions again.
Unfortunately, the 301 redirects and extensions parameters cannot be exported. But when you uninstall old version, they're preserved in your database - old JoomSEF tables just have the _bak suffix added, so you can manually restore them - namely the jos_sefexts and jos_sefmoved tables.
We could also do the whole process for you if you purchase 1 hour of our support time at:
www.artio.net/e-shop/support-services/joomla-related-support-1h 
