Registration message after saving password for first time I am using standard way of user registration. User enters default fields + some extra text fields, gets email, clicks link in email.
Back to website, he clicks one time login in button and enters password.
After saving password message pops up, which makes no sense.

"You have just used your one-time login link. It is no longer necessary to use this link to log in. Please change your password. The changes have been saved."

Why is message "Please change your password" here ?
You can use "String Overrides" module to achieve this. As this message sets using drupal_set_message function and this function stores these messages in session. So the best way to change this message is use of string overrides module. This module can easily replace anything that's passed through t() function. So you just need to put whole string that you want to replace with your own string.