Where i can add this?
Basically that depends first of all on the payment module you are using. Since I don't know what that module does or not, I'll tell you how that messages work in general.
A payment module usually has a Block which inherits from
Mage_Payment_Block_Form (usually you find a
Form.php somewhere in the
Block folder of the payment module).
In this block there is the possibility to call a method
setMethodLabelAfterHtml() which sets the message for the specific payment method (that's usually done in the constructor).
For example adding this line in the constructor of the Form Block of your payment method, look for the corresponding block and add the message
$this->setMethodLabelAfterHtml('You will be reirected to...');
in the constructor.
Please note: If you have a third party module which receives updates it's not recommended to make changes in their code. I've only tried to explain you how the message for payment methods are working.