Every time i sign into my google account on a web browser on a new machine, it warns me of suspicious activity. How does google know its a new machine? I am trying to implement a similar thing for my website, where I should allow the user to login without any notification if I know he had logged in from that machine before, whereas on the other hand, I want to notify user if the user is logging in from a new machine.
@Joe M.'s comment provides a good link as to how Google accomplishes this.
For what you are looking to accomplish simply capturing the IP address of the visitor seems like it would be effective in determining new or returning users, though this isn't enough, as multiple unique users could navigate to your site from within the same internal network (to your server this would appear as originating from the same external IP) and would need to be handled individually. If this was your only logic then you could only ever have 1 unique visitor per IP, which is probably not what you are looking for.
To handle this you would need to assign a unique cookie to each unique visitor. This works for Google because it will associate your username with this cookie. Unless you have something with which to associate the cookie (username, id, etc.) then it won't be possible because the requests could be spoofed by replicating request headers from another machine using the same external IP.
I suppose you could associate a WebGL fingerprint, which would be unique to the specific machine, and associate that along with the external IP for the cookie value.
I'm not sure on the particulars of how Google does it specifically, but it's likely to do with a combination of many factors, including your IP address, geographical location, browser fingerprint (such as User Agent and add-ons), etc.
Chances are that it is not any single one of these factors that will trigger a warning but some combination of them.
For more details see the comment I made on the post linked to by Joe M.
In order to create such a system you'll need to incorporate more information that IP address and cookies in order to not overwhelm users with false positives, as well as to persist if a user clears their cookies for whatever reason.