I just had a gmail account hacked, did a google search and it seems there are many ways to hack gmail, e.g. after you fill out some ads forms and such. This looks scary and is it time for us to do two-step login these days?
@0xexplorer is absolutely correct with both of those suggestions. You need to know where you account is being logged in from (if someone is trying) and setting up 2-factor auth won't allow someone with just the password in.
Change your account password before switching to 2-factor auth. When you do, be sure you first have a q-code reader and google authenticator on your phone. This way you can turn on their code generator as part of the process. Unless you like texts of course, but its up to you.
You should indeed enable two factor authentication and not only on gmail. It is also good practice to enable account login notifications.