OK I went and listened to that track....very nice layed back track by the way....
I am sure what he did was lay down some bkgnd vocal tracks and then auto tuned them....Then mixed them in very lightly because they are being used as effect more than anything....but it is done well....
So my suggestion would be to take and do several backing track (maybe even in simple harmony like in 3rd's) to the main vox. set up a Auto tune buss and run them thru there...then mix to taste....
Now it was suggested to sing out of key a bit to make the plug in work....the more out of key you sing the harder the plug will work....
and there is a lot of truth to that statement...........however....in this case I would not stray too far with being out of tune....just go slightly and make the plug work.....but work lightly....this way you achieve your auto tune effect but it is not over done like in a T-Pain type of way.......
and then again, maybe that is what you are going for......and if so....you know what to do now....
Clifford