Always flash latest TWRP found here:
To flash recovery use fastboot:
(some number should appear here)
fastboot flash recovery
Or you can use Flashify or similar if already rooted. But, go ahead and learn to fastboot.
(Thanks to @simms22 for telling me to clarify)
first thing you want to do is backup your EFS partition in twrp and copy it to safe place (aka your computer or some secure cloud) - thanks to @gee2012 for headsup.
So now to the ROM flashing / fun part:
Installing custom ROMS/Gapps packages (thanks to @kufikugel for headsup)
Go to Wipe -> Advanced, format system (as your previous custom ROM/Gapps has most probably added backup scripts in system/addon.d), data, cache & dalvik. reboot recovery. flash new ROM & gapps as you would usually.