I do it through the payees one day after a payment has been made.
It can usually be done online otherwise over the phone.
You don't need to inform your bank beforehand but there is no harm in cancelling the old direct debit once the new payment has gone through successfully.
All the payee needs to know is the new bank details.