First I always said "вы ", but after a couple of times of being told to stop being so formal, i got used to ты and fell into a bad habit of using it all the time.
For foreigners, I think the best practice is to use вы all the time and not even think of asking Можно на ты? until your new Russian friend invites you to use it: "Давай на ты, kidkboom!" (The exception to this would be if you're a foreign adult speaking to young children, in which case you should speak to them на ты from the very beginning.)