To get the most out of the new Nether update, you can reset the Nether dimension of your server so that new biomes and structures can be generated.
Warning: Resetting the Nether will delete everything you built there. You should create a backup first, in case you want to go back.
Vanilla, Forge, and Arclight
servers store dimensions as subfolders of your main world folder. To reset the Nether, open your world files, and delete the 'DIM-1' folder. This should only be done while your server is offline.
Make sure to not accidentally delete 'DIM1' instead of 'DIM-1', since this would reset the End dimension instead of the Nether.
Spigot and Paper
Bukkit-based servers store all dimensions as separate worlds. To reset the Nether, delete 'world_nether' on the worlds page.
If the name of your main world is not 'world', delete '{name-of-main-world}_nether'.